深さ優先探索との比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/12/06 02:42 UTC 版)
「反復深化深さ優先探索」の記事における「深さ優先探索との比較」の解説
メモリに載りきらないような大規模な木を探索する場合、深さ優先探索は探索木のパスの長さが長くなりすぎて探索が終わらないという問題を抱えている。「訪れたノードを記憶する」という単純な方法は、十分なメモリ量がない場合通用しなくなるのである。また、探索対象が木ではなく一般の有向グラフである場合(特に、ループを含む場合)にも同じ問題が起こる。これは、木の深さを段階的に増やして探索する反復深化深さ優先探索で解決することができる。 下記の図を用いた場合、 グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することにより再訪しないとするならば、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を見つけていることに注意。Eを別のパスでみつけていることとFでループを見つけていることにも注意。) 3: A, B, D, F, E, C, G, E, F, B このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。
※この「深さ優先探索との比較」の解説は、「反復深化深さ優先探索」の解説の一部です。
「深さ優先探索との比較」を含む「反復深化深さ優先探索」の記事については、「反復深化深さ優先探索」の概要を参照ください。
- 深さ優先探索との比較のページへのリンク
