深さ制限探索
From Wikipedia, the free encyclopedia
通常の深さ優先探索のように、深さ制限探索も一様な探索を行う。深さ優先探索と異なるのは、探索する深さを制限する点である。制限を越えて探索木を深くしていくことがないため、無限の経路に捉われたり、環状の経路に捉われたりすることがない。従って、深さ制限探索は制限された深さの範囲内で、あらゆるグラフの最適解を求めることができる。
アルゴリズム（木構造の場合）
- 探索の始点となるノードを決定し、探索すべき深さの上限を決定する。
- 現在のノードが目標とする状態かどうか調べる。
- 目標状態の場合: 探索成功。終了する。
- 現在のノードが探索すべき深さの範囲内にあるか調べる。
- 範囲内の場合: ノードを展開し、深さ制限探索を再帰的に呼び出し、ステップ2に戻る。
- 探索失敗
木構造ではなく一般のグラフの場合、訪問済みのノードかどうかを管理すべき。ただし、深さ優先探索とは異なり、閉路があっても、無限ループに陥ることはない。また、訪問済みのノードを管理するとメモリ不足に陥る場合は、諦めるか、量を制限するかなどをする。
