指定された深度レベルでノードをスキャンするだけでなく、繰り返し深化を行う方が効率的です。

Question

反復ごとにn-1レベルのノードを再スキャンするのは冗長ではありませんか？

Answer 1

私はArtificial Intelligence: A Modern Approachから引用：状態が複数回発生しているため

反復深化の検索が無駄に見えるかもしれません。これはあまりにも高価ではないことが判明しました。その理由は、各レベルで同じ（またはほぼ同じ）分岐ファクタを持つ検索ツリーでは、ほとんどのノードがボトムレベルにあるため、上位レベルが複数回生成されることはあまり重要ではないからです。反復深化検索では、最下位レベル（深さd）のノードが1回生成され、最下位レベルのノードが2回生成され、以下同様に、生成されたルートの子ノードまでd回。だから、最悪の場合に生成されたノードの総数は

N（IDS）=（D）は* B +（D-1）* B^2 + ... +（1）* B^D

これは、O（b^d）の時間的複雑さを与え、幅優先探索と漸近的に同じである。