幅優先探索

幅優先探索
	Order in which the nodes get expanded; 探索順
General Data
Class:	探索アルゴリズム
データ構造:	グラフ
時間計算量:	V\|+\|E\|)</math>
空間計算量:	V\|+\|E\|)</math>
Optimal:	yes
Complete:	yes

幅優先探索(Breadth first search)はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられる。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。

どう動作するか

形式としては、幅優先探索は解を探すために、グラフの全てのノードをシステマティックに展開・検査することを狙う方法である。つまり、グラフ全体を目的のノードがみつかるまで、目的のノードについて考慮せず徹底的に探索するのである。ノード探索にヒューリスティクス(heuristic)は使われない。

アルゴリズムの観点からだと、ノードの展開により得られる子はキューに追加される。典型的な実装の場合、未訪のノードは"open"と名づけられた(キューや連結リストのような)コンテナに格納され、既訪のノードは"closed"と名づけられたコンテナに格納されることになる。

ファイル:MapGermanyGraph.svg

ドイツの都市間の接続を示した例

ファイル:GermanyBFS.svg

フランクフルトから幅優先検索を行った場合にできる木構造

アルゴリズム

根ノードを空のキューに加える。
ノードをキューの先頭から取り出し、以下の処理を行う。
- ノードが探索対象であれば、探索をやめ結果を返す。
- そうでない場合、ノードの子で未探索のものを全てキューに追加する。
もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す。
2に戻る。

擬似コード

v は頂点。

幅優先探索(v)
    v に訪問済みの印を付ける
    v をキューに追加
    while (キューに要素を含むなら)
        v ← キューから取り出す
        v を処理
        for each (v に接続していて かつ 未訪問の頂点 i)
            i に訪問済みの印を付ける
            i をキューに追加

Common Lisp でのコード例

(defun bfs (node target)
  (do ((queue (list node)
	      (append (cdr queue)
		      (get (car queue) 'subnodes)))
       (ls nil (if (get (car queue) target)
		   (cons (car queue) ls)
		   ls)))
      ((null queue) (reverse ls))))

アルゴリズムの特徴

空間計算量

見つかったノードを全て記録する必要があるので、幅優先探索の空間計算量はO(|V| + |E|)となる。ここで|V|はグラフ内のノードの数で|E|は辺の数である。または、<math>O(B ^ M)</math>ということができる。ここでBは枝分かれの最大数でMは木の最長経路の長さである。この量の巨大さは幅優先探索が規模の大きな探索において非現実的な理由である。

時間計算量

最悪の場合、幅優先探索は全ての経路とノードを考慮に入れる必要があるので、幅優先探索の時間計算量はO(|V| + |E|)である。ここで、|V|はグラフ内のノードの数で|E|はグラフ内の辺の数である。

完全性

幅優先探索は完全である。つまり、解が存在する場合はグラフによらず解をみつけることができるということである。しかしながら、グラフが無限で探索対象の解が存在しない場合、幅優先探索は終了しない。

最適性

一般に幅優先探索は最適で、常に開始ノードと終了ノードの長さが最も少ない辺を返す。もしグラフが重みつきならば、最初のノードの隣のノードが最良のゴールとは限らないが、この問題は辺のコストを考慮に入れた均一コスト探索(Uniform cost search)で解決できる。