|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 深さ ： [ふかさ] 【名詞】 1. depth 2. profundity ・ 制 ： [せい] 1. (n,n-suf,vs) system 2. organization 3. organisation 4. imperial command 5. laws 6. regulation 7. control 8. government 9. suppression 10. restraint 1 1. holding back 12. establishment 1 ・ 制限 ： [せいげん] 1. (n,vs) restriction 2. restraint 3. limitation ・ 探索 ： [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 索 ： [さく] 【名詞】 1. rope 2. cord
深さ制限探索（ふかさせいげんたんさく、）とは、グラフの頂点を探索するアルゴリズムの一種である。深さ優先探索からの派生であり、反復深化深さ優先探索アルゴリズムなどで使う。 == 概要 == 通常の深さ優先探索のように、深さ制限探索も一様な探索を行う。深さ優先探索と異なるのは、探索する深さを制限する点である。制限を越えて探索木を深くしていくことがないため、無限の経路に捉われたり、環状の経路に捉われたりすることがない。従って、深さ制限探索は制限された深さの範囲内で、あらゆるグラフの最適解を求めることができる。 == アルゴリズム（木構造の場合） == # 探索の始点となるノードを決定し、探索すべき深さの上限を決定する。 # 現在のノードが目標とする状態かどうか調べる。 # * 目標状態の場合: 探索成功。終了する。 # 現在のノードが探索すべき深さの範囲内にあるか調べる。 # * 範囲内の場合: ノードを展開し、深さ制限探索を再帰的に呼び出し、ステップ2に戻る。 # 探索失敗 木構造ではなく一般のグラフの場合、訪問済みのノードかどうかを管理すべき。ただし、深さ優先探索とは異なり、閉路があっても、無限ループに陥ることはない。また、訪問済みのノードを管理するとメモリ不足に陥る場合は、諦めるか、量を制限するかなどをする。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「深さ制限探索」の詳細全文を読む スポンサード リンク
|