反復深化深さ優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

反復深化深さ優先探索: iterative deepening depth-first search、IDDFS)とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば(刈り込みがない場合)、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。

概要[編集]

IDDFSは深さ優先探索のメモリ効率と幅優先探索の完全性(分岐が有限の場合)を併せ持っている。ノードの深さに対応して経路コストが減少しない場合、これが最適とされている。

IDDFSの空間計算量O(bd) であり、b分岐係数d は深さである。木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。

ゲーム木でIDDFSを使う場合、アルファ・ベータ枝刈りなどのヒューリスティックが反復によって改善されていき、最も深い探索でのスコアの推定値がより正確になるという利点がある。また、探索順序を改善することができるため、探索をより高速に行えるという利点もある(前の反復で最善とされた手を次の反復で最初に調べることでアルファ・ベータ法の効率が良くなる)。

また、このアルゴリズムは応答性がよいという利点もある。初めの反復では d が小さいので高速に完了する。このためこのアルゴリズムは素早く大まかな結果を示しつつ、d を深くすることでそれをさらに洗練させていくことができる。チェスプログラムのような対話型プログラムでは、任意の時点で探索を打ち切って、その時点で最善と思われる手を示すことができるという利点がある。これは通常の深さ優先探索では不可能である。

IDDFSの時間計算量は、平衡のとれた木では深さ優先探索と同じ O(b^{d}) である。

反復深化探索では、底辺レベルのノードは1回展開され、その1つ上のレベルのノードは2回、根ノードは d+1 回展開される。したがって総展開回数は次のようになる。

(d + 1)1 + (d)b + (d-1)b^{2} + ... + 3b^{d-2} + 2b^{d-1} + b^{d}

例えば b=10d=5 の場合、具体的には次のようになる。

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

これは、幅優先探索や深さ制限探索を行ったときのノード展開回数に対して11%の増加にしかならない。分岐係数が大きくなればオーバーヘッドも小さくなるが、分岐係数が2だったとしても、幅優先探索の2倍にしかならない。そのため、時間計算量は O(b^{d}) で、空間計算量は O(bd) となる。一般に、探索空間が広く深さが未知の場合、反復深化深さ優先探索が最も好ましい方法とされている[1]

関連アルゴリズム[編集]

類似の探索戦略として、深さ制限ではなく経路コスト制限を変化させて反復する iterative lengthening search がある。この場合、ノードは経路コストを増大させるような形でノードを展開していく。したがって、最も経路コストが低いものが目標とされる。しかし、オーバーヘッドが大きいため、反復深化ほど有用ではない。

脚注[編集]

  1. ^ Russell, Stuart J. & Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2