反復深化法(繰り返し縦型探索)
Iterative deepening Search
反復深化探索アルゴリズム
深さ限度を表す変数(初期値0)により深さ優先探索を制 御す
る方法．
c ← 0;
L ← [n
0
];
repeat
while
L = [ ]
do
begin
c ← c + 1;
L ← [n
0
];
end
n ← pop(L);
if
P(n)
then exit
(<成功:n
0
からnまでの経路>);
if
(depthOf(n) < c)
then
<
nの全ての子供をLの先頭に追加
し，それぞれに初期 ノードからの経路を対応付ける>;
until false
特徴
探索するノードを再生成するコストが小さい場合は有効．
完全性: yes
最適性: yes
時間計算量
O
(b
s
)
空間計算量
O
(bs)
...Return
講義ノートインデックス
...Return