反復深化深さ優先探索
反復深化深さ優先探索（Iterative Deepening Depth-First Search, IDDFS）は、探索アルゴリズムの一種で、深さ制限探索の制限を段階的に増加させながら、目標状態の深さに達するまで反復する手法です。各反復では深さ優先探索の順序でノードを探索しますが、全体として見ると（刈り込みがない場合）、最初にノードを調べる順序は幅優先探索と同じになります。IDDFSを知識あり探索に応用したものがIDAであり、これはダイクストラ法を知識あり探索にしたAに対応します。
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=10`、`d=5`の場合、総展開回数は`6 + 50 + 400 + 3000 + 20000 + 100000 = 123456`となります。これは、幅優先探索や深さ制限探索を行った場合のノード展開回数に対して11%の増加に過ぎません。分岐係数が大きくなるほどオーバーヘッドは小さくなり、分岐係数が2の場合でも幅優先探索の2倍程度に収まります。このため、時間計算量は`O(b^d)`、空間計算量は`O(bd)`となります。一般的に、探索空間が広く深さが未知の場合、反復深化深さ優先探索が最も有効な手法とされています。
メモリに乗り切らないほど大規模な木を探索する場合、深さ優先探索は探索パスが長くなりすぎて探索が終わらないという問題を抱えています。「訪れたノードを記憶する」という単純な方法も、十分なメモリがない場合は利用できません。また、探索対象が木ではなく一般的な有向グラフ（特にループを含む場合）でも同様の問題が発生します。これらの問題は、深さを段階的に増やして探索する反復深化深さ優先探索で解決することができます。
例えば、以下の図のようなグラフを考えます。
A
/|\
B C E
/ | \
D G F
F B
グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することで再訪しないと仮定した場合、Aからスタートした深さ優先探索は、A, B, D, F, E, C, Gという順序でノードを訪れます。しかし、以前訪れたノードを記憶しない場合、A, B, D, F, E, A, B, D, F, E... とループに陥り、永遠にCやGに到達できません。
反復深化はこのループを回避し、左から右に探索が進むと仮定した場合、以下の深さで各ノードに到達します。
このように、深さを増やすたびにアルゴリズムは探索を中断し、他の枝に移るまでループが長くなっていきます。
function IDDFS(node)
for (depth = 0; ; depth++)
found = DLS(node, depth)
if (found != NULL) then
return found
function DLS(node, depth)
if (IS_GOAL(node)) then
return node
if (depth > 0) then
for each (child in EXPAND(node))
found = DLS(child, depth - 1)
if (found != NULL) then
return found
return NULL
ここで、`EXPAND(node)`はノード展開関数で、探索候補の集合を返します。`IS_GOAL(node)`はノード探索終了判定関数で、ゴールに到達したかどうかを判定します。`DLS`は深さ制限探索を表します。
類似の探索戦略として、深さ制限ではなく経路コスト制限を変化させて反復する反復伸長探索（Iterative Lengthening 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=10`、`d=5`の場合、総展開回数は`6 + 50 + 400 + 3000 + 20000 + 100000 = 123456`となります。これは、幅優先探索や深さ制限探索を行った場合のノード展開回数に対して11%の増加に過ぎません。分岐係数が大きくなるほどオーバーヘッドは小さくなり、分岐係数が2の場合でも幅優先探索の2倍程度に収まります。このため、時間計算量は`O(b^d)`、空間計算量は`O(bd)`となります。一般的に、探索空間が広く深さが未知の場合、反復深化深さ優先探索が最も有効な手法とされています。
深さ優先探索との比較
メモリに乗り切らないほど大規模な木を探索する場合、深さ優先探索は探索パスが長くなりすぎて探索が終わらないという問題を抱えています。「訪れたノードを記憶する」という単純な方法も、十分なメモリがない場合は利用できません。また、探索対象が木ではなく一般的な有向グラフ（特にループを含む場合）でも同様の問題が発生します。これらの問題は、深さを段階的に増やして探索する反復深化深さ優先探索で解決することができます。
例えば、以下の図のようなグラフを考えます。
A
/|\
B C E
/ | \
D G F
グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することで再訪しないと仮定した場合、Aからスタートした深さ優先探索は、A, B, D, F, E, C, Gという順序でノードを訪れます。しかし、以前訪れたノードを記憶しない場合、A, B, D, F, E, A, B, D, F, E... とループに陥り、永遠にCやGに到達できません。
反復深化はこのループを回避し、左から右に探索が進むと仮定した場合、以下の深さで各ノードに到達します。
- - 深さ0: A
- - 深さ1: A (反復), B, C, E
- - 深さ2: A, B, D, F, C, G, E, F
- - 深さ3: A, B, D, F, E, C, G, E, F, B
このように、深さを増やすたびにアルゴリズムは探索を中断し、他の枝に移るまでループが長くなっていきます。
擬似コード
function IDDFS(node)
for (depth = 0; ; depth++)
found = DLS(node, depth)
if (found != NULL) then
return found
function DLS(node, depth)
if (IS_GOAL(node)) then
return node
if (depth > 0) then
for each (child in EXPAND(node))
found = DLS(child, depth - 1)
if (found != NULL) then
return found
return NULL
ここで、`EXPAND(node)`はノード展開関数で、探索候補の集合を返します。`IS_GOAL(node)`はノード探索終了判定関数で、ゴールに到達したかどうかを判定します。`DLS`は深さ制限探索を表します。
関連アルゴリズム
類似の探索戦略として、深さ制限ではなく経路コスト制限を変化させて反復する反復伸長探索（Iterative Lengthening Search）があります。この場合、ノードは経路コストを増大させるように展開され、最も経路コストの低いものが目標とされます。しかし、オーバーヘッドが大きいため、反復深化ほど有用ではありません。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。