幅優先探索

幅優先探索( BFS ) は、ツリーデータ構造内で特定のプロパティを満たすノードを検索するアルゴリズムです。ツリーのルートから開始し、現在の深さにあるすべてのノードを探索してから、次の深さレベルのノードに進みます。遭遇したがまだ探索されていない子ノードを追跡するには、追加のメモリ (通常はキュー) が必要です。

たとえば、チェスの終盤では、チェスエンジンは、すべての可能な動きを適用して現在の位置からゲームツリーを構築し、幅優先探索を使用して白の勝利位置を見つけます。暗黙のツリー（ゲームツリーやその他の問題解決ツリーなど）は無限のサイズになる場合があります。幅優先探索では、ソリューションノード^[1]が存在する場合は必ず見つかります。

対照的に、（単純な）深さ優先探索（DFS）は、他のノードをバックトラックして拡張する前に、可能な限りノードブランチを探索しますが、^[2]無限ブランチで迷子になり、ソリューションノードに到達できない可能性があります。反復深化深さ優先探索は、ツリーの上部を何度も探索するという代償を払って、後者の欠点を回避します。一方、両方の深さ優先アルゴリズムは、通常、幅優先探索よりもはるかに少ない追加メモリを必要とします。^[3]

幅優先探索は、無向グラフと、与えられた開始ノード（「検索キー」と呼ばれることもある）を持つ有向グラフの両方に一般化することができる。 ^[4]人工知能における状態空間探索では、頂点の繰り返し探索がしばしば許可されるが、幅優先探索に基づくアルゴリズムの理論的分析では、通常、繰り返しを防ぐための予防措置が講じられる。

BFS とグラフの連結成分を見つけるためのその応用は、1945 年にKonrad ZuseによってPlankalkülプログラミング言語に関する博士論文 (却下) の中で発明されましたが、これは 1972 年まで公開されませんでした。 ^{[5]これは 1959 年に}Edward F. Mooreによって再発明され、迷路からの最短経路を見つけるために使用されました。^{[6] [7]}その後、CY Lee によって配線ルーティングアルゴリズムに開発されました (1961 年に公開)。^[8]

入力: グラフGとGの開始頂点 ルート

出力：ゴール状態。親リンクはルートへの最短経路を辿る^[9]

1  手順BFS( G , root )は
 2 Qをキューとする3探索された
 ラベルルート
 4       Q .enqueue(ルート)
 5       Qが空でない間に 
 6           v  := Q .dequeue()を実行する
 7           vが ゴールなら
 8               vを返す9 G .adjacentEdges( v )のvからwへのすべての辺に対して
 10          
を              実行するwが探索済みとしてラベル付けされていない場合は11 
wを探索済みとしてラベル付けする    
12                   w .parent := v 
13                   Q .enqueue( w )

この非再帰実装は、深さ優先探索の非再帰実装に似ていますが、次の 2 つの点で異なります。

1. スタック（後入れ先出し）の代わりにキュー（先入れ先出し）を使用し、
2. 頂点がキューからデキューされるまでこのチェックを遅らせるのではなく、頂点をキューに入れる前に頂点が探索されたかどうかをチェックします。

Gが木の場合、この幅優先探索アルゴリズムのキューをスタックに置き換えると、深さ優先探索アルゴリズムが生成されます。一般的なグラフの場合、反復深さ優先探索実装のスタックをキューに置き換えると、やや非標準的ではありますが、幅優先探索アルゴリズムが生成されます。^[10]

Qキューには、アルゴリズムが現在検索している境界が含まれています。

実装に応じて、ノードをセットに格納するか、各ノードの属性によって、ノードを探索済みとしてラベル付けできます。

「ノード」という単語は通常、 「頂点」という単語と置き換え可能であることに注意してください。

各ノードの親属性は、BFS が実行され、先行ノードが設定された後、宛先ノードから開始ノードまでバックトラックするなど、最短パスでノードにアクセスするのに役立ちます。

幅優先探索は、いわゆる幅優先ツリーを生成します。次の例で 幅優先ツリーがどのように見えるかを確認できます。

以下は、フランクフルトから始まるドイツの都市に対して BFS を実行して得られた幅優先ツリーの例です。

最悪の場合、すべての頂点とすべての辺が探索されるため、時間計算量は と表すことができます。はグラフの頂点の数、はグラフの辺の数です。入力グラフの疎度に応じて、は との間で変化する可能性があることに注意してください。^[11]${\displaystyle O(|V|+|E|)}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle O(|E|)}$${\displaystyle O(1)}$${\displaystyle O(|V|^{2})}$

グラフ内の頂点の数が事前にわかっていて、どの頂点がすでにキューに追加されているかを判断するために追加のデータ構造が使用される場合、空間計算量はと表現できます。ここで、は頂点の数です。これは、グラフ自体に必要な空間に加えて必要となるもので、アルゴリズムの実装で使用される グラフ表現に応じて異なる場合があります。${\displaystyle O(|V|)}$${\displaystyle |V|}$

明示的に保存するには大きすぎる（または無限大の）グラフを扱う場合、幅優先探索の複雑さを別の言葉で説明する方が実用的です。開始ノードから距離dにあるノード（エッジトラバーサルの数で測定）を見つけるには、BFS はO ( b ^{d + 1} )の時間とメモリを要します。ここで、b はグラフの「分岐係数」（平均出次数）です。^{[12] : 81}

アルゴリズムの分析では、幅優先探索への入力は、隣接リスト、隣接行列、または同様の表現として表される有限グラフであると想定されます。ただし、人工知能におけるグラフトラバーサル法の適用では、入力は無限グラフの暗黙的な表現である可能性があります。この文脈では、目標状態が存在する場合にそれを見つけることが保証されている場合、探索方法は完全であると説明されます。幅優先探索は完全ですが、深さ優先探索は完全ではありません。暗黙的に表現された無限グラフに適用すると、幅優先探索は最終的に目標状態を見つけますが、深さ優先探索は目標状態がなく、二度と戻らないグラフの部分で失われる可能性があります。^[13]

グラフの頂点の列挙は、それがこのグラフに BFS を適用した際の可能な出力である場合、BFS 順序付けであると言われます。

を頂点を持つグラフとします。はの近傍の集合であることを思い出してください。を の異なる要素のリストとします。に対して、が存在する場合、が の近傍となるような最小の を とし、そうでない場合 とします。 ${\displaystyle G=(V,E)}$${\displaystyle n}$${\displaystyle N(v)}$${\displaystyle v}$${\displaystyle \sigma =(v_{1},\dots ,v_{m})}$${\displaystyle V}$${\displaystyle v\in V\setminus \{v_{1},\dots ,v_{m}\}}$${\displaystyle \nu _{\sigma }(v)}$${\displaystyle i}$${\displaystyle v_{i}}$${\displaystyle v}$${\displaystyle i}$${\displaystyle \infty }$

を の頂点の列挙とします。すべての に対してがが最小となる頂点である場合、列挙はBFS 順序付け (ソース を含む)であるといわれます。同様に、のすべての に対して となるの隣接頂点が存在する 場合、 は BFS 順序付けです。 ${\displaystyle \sigma =(v_{1},\dots ,v_{n})}$${\displaystyle V}$${\displaystyle \sigma }$${\displaystyle v_{1}}$${\displaystyle 1<i\leq n}$${\displaystyle v_{i}}$${\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}$${\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}$${\displaystyle \sigma }$${\displaystyle 1\leq i<j<k\leq n}$${\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}$${\displaystyle v_{m}}$${\displaystyle v_{j}}$${\displaystyle m<i}$

幅優先探索は、グラフ理論の多くの問題を解決するために使用できます。たとえば、次のようになります。

• コピーガベージコレクション、チェイニーのアルゴリズム
• 2つのノードuとvの間の最短経路を見つける。経路の長さはエッジの数で測定される（深さ優先探索よりも優れている）^[14]
• （逆）カットヒル・マッキーメッシュ番号
• フローネットワークの最大フローを計算するためのフォード・フルカーソン法
• バイナリ ツリーのシリアル化/デシリアル化とソート順でのシリアル化により、ツリーを効率的に再構築できます。
• Aho-Corasickパターン マッチャーの失敗関数の構築。
• グラフの二部性をテストします。
• グラフの推移閉包を計算するための並列アルゴリズムの実装。^[15]

• 深さ優先探索
• 反復深化深さ優先探索
• レベル構造
• 辞書式幅優先探索
• 並列幅優先探索

• オープン データ構造 - セクション 12.3.1 - 幅優先探索、Pat Morin