|
反復深化深さ優先探索（英: iterative deepening depth-first search、IDDFS）とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば（刈り込みがない場合）、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。 IDDFSを知識あり探索にしたものがIDA *である。これは、ダイクストラ法を知識あり探索にしたものがA *であることに対応する。 == 概要 == IDDFSは深さ優先探索のメモリ効率と幅優先探索の完全性（分岐が有限の場合）を併せ持っている。ノードの深さに対応して経路コストが減少しない場合、これが最適とされている。 IDDFSの空間計算量は であり、 は分岐係数、 は深さである。木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。 ゲーム木でIDDFSを使う場合、アルファ・ベータ枝刈りなどのヒューリスティックが反復によって改善されていき、最も深い探索でのスコアの推定値がより正確になるという利点がある。また、探索順序を改善することができるため、探索をより高速に行えるという利点もある（前の反復で最善とされた手を次の反復で最初に調べることでアルファ・ベータ法の効率が良くなる）。 また、このアルゴリズムは応答性がよいという利点もある。初めの反復では が小さいので高速に完了する。このためこのアルゴリズムは素早く大まかな結果を示しつつ、 を深くすることでそれをさらに洗練させていくことができる。チェスプログラムのような対話型プログラムでは、任意の時点で探索を打ち切って、その時点で最善と思われる手を示すことができるという利点がある。これは通常の深さ優先探索では不可能である。 IDDFSの時間計算量は、平衡のとれた木では深さ優先探索と同じ である。 反復深化探索では、底辺レベルのノードは1回展開され、その1つ上のレベルのノードは2回、根ノードは 回展開される。したがって総展開回数は次のようになる。 例えば で の場合、具体的には次のようになる。 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456 これは、幅優先探索や深さ制限探索を行ったときのノード展開回数に対して11%の増加にしかならない。分岐係数が大きくなればオーバーヘッドも小さくなるが、分岐係数が2だったとしても、幅優先探索の2倍にしかならない。そのため、時間計算量は で、空間計算量は となる。一般に、探索空間が広く深さが未知の場合、反復深化深さ優先探索が最も好ましい方法とされている〔Russell, Stuart J. & Norvig, Peter (2003), ''Artificial Intelligence: A Modern Approach'' (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2〕。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「反復深化深さ優先探索」の詳細全文を読む スポンサード リンク
|