深さ制限探索
Depth Bounded (or Limited) Search
深さ制限探索アルゴリズム
深さ優先探索に，
調べる深さの制限
を設 けた方法． 以下ではその限界値を l とする．
L ← [n
0
];
while
L ≠[ ]
do
begin
n ← pop(L);
if
P(n)
then exit
(<成功:n
0
からn までの経路>);
if
(depthOf(n) < l)
then
begin
d ← <nにOの各要素を適用して得られる全ての状態に対 応するノードのリスト>;
L ← append(d, L);
end
end
特徴
深さの制限の見積もりが可能な場合は有効．見積もりを誤ると解が見つ からない．
完全性: yes (s を解の深さとして，l ≧ s のとき)
最適性: no
時間計算量
O
(b
l
)
空間計算量
O
(bl)
...Return
講義ノートインデックス
...Return