「深さ優先探索」の版間の差分

形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードは[[スタック]]に追加される。

 

 

メモリに載りきらないような大規模なグラフを探索する場合、深さ優先探索は探索木のパスの長さが長くなりすぎて探索が終わらないという問題を抱えている。「訪れたノードを記憶する」という単純な方法は、十分なメモリ量がない場合通用しなくなるのである。これは、木の深さを段階的に増やして探索する[[反復深化深さ優先探索]]([[:en:iterative deepening depth-first search]])と呼ばれるアルゴリズムで解決することができる。

 

このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。

 

==擬似コード(再帰的)==