幅優先探索 (横型探索)
Breadth-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(L,d);
end
演習問題
特徴
解が複数ある場合に最も浅い解をみつける．
完全性: yes
最適性: yes (ただし経路コストがノードの深さに対して非減少関数かつ すべての操作が同じ場合)
時間計算量
O
(b
s
) (s は解の深さ，bは分岐度(branching factor))
空間計算量
O
(b
s
)
幅優先探索の時間とメモリの必要量
深さ
ノード数
時間
メモリ
0
1
1ミリ秒
100バイト
2
111
0.1秒
11Kバイト
4
11,111
11秒
1Mバイト
6
10
6
18分
111Mバイト
8
10
8
31時間
11Gバイト
10
10
10
128日
1Tバイト
12
10
12
35年
111Tバイト
(分岐度 b = 10, 1,000ノード/秒，100バイト/ノードを仮定)
...Return
講義ノートインデックス
...Return
...Return