深さ優先探索 (縦型探索)
Depth-first Search
深さ優先探索アルゴリズム
初期ノードからはじめて，
最も長い経路から調べ ていく
方法．
L ← [n
0
];
while
L ≠[ ]
do
begin
n ← pop(L);
if
P(n)
then exit
(<成功:n
0
からn までの経路>);
d ← <nにOの各要素を適用して得られる全ての状態に対応するノードのリスト>;
L ← append(d, L);
end
特徴
一つも解が見つけられない場合がある
完全性: no
最適性: no
時間計算量
O
(b
m
) (mは探索木の最大の深さ)
空間計算量
O
(bm)
...Return
講義ノートインデックス
...Return