反復深化深さ優先探索
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/02/11 09:13 UTC 版)
反復深化深さ優先探索(はんぷくしんかふかさゆうせんたんさく、英語: iterative deepening depth-first search、IDDFS)とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば(刈り込みがない場合)、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。
IDDFSを知識あり探索にしたものがIDA*である。これは、ダイクストラ法を知識あり探索にしたものがA*であることに対応する。
概要
IDDFSは深さ優先探索のメモリ効率と幅優先探索の完全性(分岐が有限の場合)を併せ持っている。ノードの深さに対応して経路コストが減少しない場合、これが最適とされている。
IDDFSの空間計算量は
グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することにより再訪しないとするならば、Aからスタートした深さ優先探索はA, B, D, F, E, C, Gという順番で訪れる。
ここで以前訪れたノードを記憶していない場合、A, B, D, F, E, A, B, D, F, Eと、A, B, D, F, Eのループに捕まって永遠にCやGに到達することはできない。
反復深化はこのループを回避し、上記のように左から右に探索が進むとすると、下記の深さにおいて下記のノードに到達する。
- 0: A
- 1: A (repeated), B, C, E
(反復深化はCをみつけていることに注意。通常の深さ優先探索では見つからない。)
- 2: A, B, D, F, C, G, E, F
(以前Cを見つけていることに注意。Fを別のパスでみつけていることとFでループを見つけていることにも注意。)
- 3: A, B, D, F, E, C, G, E, F, B
このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。
擬似コード
- EXPAND(node)
- ノード展開関数:探索候補の集合を返す。
- IS_GOAL(node)
- ノード探索終了判定関数:ゴールに到達したかどうか。
DLS は深さ制限探索。
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
関連アルゴリズム
類似の探索戦略として、深さ制限ではなく経路コスト制限を変化させて反復する iterative lengthening search がある。この場合、ノードは経路コストを増大させるような形でノードを展開していく。したがって、最も経路コストが低いものが目標とされる。しかし、オーバーヘッドが大きいため、反復深化ほど有用ではない。
脚注
- ^ Russell, Stuart J. & Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2
- 反復深化深さ優先探索のページへのリンク