幅優先探索

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
幅優先探索
ノードが展開される順序
ノードが展開される順序
クラス検索アルゴリズム
データ構造グラフ
最悪の場合の パフォーマンス
最悪の場合の スペースの複雑さ
幅優先探索のアニメーション例。黒:探索済み、灰色:後で探索するためにキューに入れられます
三目並べゲームツリーの上部

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

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

対照的に、他のノードをバックトラックして拡張する前にノードブランチを可能な限り探索する(単純な)深さ優先探索[2]は、無限ブランチで失われ、ソリューションノードに到達しない可能性があります。深さ優先探索を繰り返すことで、ツリーの上部を何度も探索するという犠牲を払って、後者の欠点を回避できます。一方、両方の深さ優先アルゴリズムは、余分なメモリなしでうまくいきます。

幅優先探索は、開始ノード(「検索キー」と呼ばれることもあります)[3]が明示的に指定されている場合、グラフに一般化でき、頂点を2回追跡しないように注意が払われます。

BFSとグラフの連結成分を見つけるためのそのアプリケーションは、1945年にKonrad Zuseによって彼の(拒否された)博士号で発明されました。プランカルキュールプログラミング言語に関する論文ですが、これは1972年まで公開されませんでした。[4] 1959年に、迷路からの最短経路を見つけるために使用したエドワードF.ムーアによって再発明されました[5] [6]以降。 CY Leeによってワイヤールーティングアルゴリズムに開発されました(1961年公開)。[7]

擬似コード

入力:グラフGG開始頂点 ルート

出力:目標の状態。リンクは、ルートまでの最短パスをトレースします[8]

1  プロシージャBFS(Groot
 2ですQをキューにします探索された
 3ラベルルート
 4       Q .enqueue(root
 5       Qが空でないときに、6  
 v             = Q .dequeue()を実行します。
 7           v目標場合  
 8              Gvからwまですべてエッジに対してv9返し
 ます          _ 
_               _    
12                   Q .enqueue(w

詳細

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

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

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

Qキューには、アルゴリズムが現在検索しているフロンティアが含まれています。

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

単語ノードは通常、単語頂点と交換可能であることに注意してください

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

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

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

都市間の接続を含む南ドイツの地図の例
指定されたマップでBFSを実行し、フランクフルトで開始したときに取得された幅優先ツリー

分析

時間と空間の複雑さ

時間計算量は次のように表すことができます、最悪の場合、すべての頂点とすべてのエッジが探索されるためです。は頂点の数であり、グラフのエッジの数です。ご了承くださいの間で異なる場合があります、入力グラフのスパース度によって異なります。[10]

グラフ内の頂点の数が事前にわかっていて、追加のデータ構造を使用して、どの頂点がすでにキューに追加されているかを判別する場合、スペースの複雑さは次のように表すことができます。、 どこは頂点の数です。これは、グラフ自体に必要なスペースに追加されるものであり、アルゴリズムの実装で使用される グラフ表現によって異なる場合があります。

大きすぎて明示的に(または無限に)格納できないグラフを操作する場合は、幅優先探索の複雑さをさまざまな用語で説明する方が実用的です。開始ノードから距離dにあるノードを見つける(数で測定)エッジトラバーサルの場合)、BFSはOb d + 1の時間とメモリを必要とします。ここで、bはグラフの「分岐係数」(平均アウトディグリー)です。[11] :81 

完全性

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

BFSの順序付け

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

させてグラフになります頂点。それを思い出しますの隣人のセットですさせての個別の要素のリストである、 ために、 させて少なくともそのようなの隣人です、そのような場合存在し、それ以外は。

させての頂点の列挙である列挙BFS注文と言われています(ソース付き))もし、すべてのために頂点ですそのような最小限です。同等に、すべての場合、BFS注文です、隣人がいる そのような

アプリケーション

幅優先探索は、グラフ理論の多くの問題を解決するために使用できます。次に例を示します。

も参照してください

参照

  1. ^ つまり、指定されたプロパティを満たすノード
  2. ^ コーメントーマスH.; etal。(2009)。「22.3」。アルゴリズムの概要MITプレス。
  3. ^ 「Graph500ベンチマーク仕様(スーパーコンピューターのパフォーマンス評価)」Graph500.org、2010年。2015年3月26日のオリジナルからアーカイブ2015年3月15日取得
  4. ^ Zuse、Konrad(1972)、DerPlankalkül(ドイツ語)、Konrad Zuse Internet Archiveリンクされたpdfファイルの96〜105ページを参照してください(内部番号2.47〜2.56)。
  5. ^ ムーア、エドワードF.(1959)。「迷路を通る最短経路」。スイッチング理論に関する国際シンポジウムの議事録ハーバード大学出版局。pp。285–292。コーメン、ライザーソン、リベスト、スタインが引用したように。
  6. ^ スキーナ、スティーブン(2008)。「ソートと検索」。アルゴリズム設計マニュアルスプリンガー。p。480. Bibcode2008adm..book.....S土井10.1007/978-1-84800-070-4_4ISBN 978-1-84800-069-8
  7. ^ リー、CY(1961)。「パス接続のアルゴリズムとその応用」。電子計算機でのIREトランザクション土井10.1109/TEC.1961.5219222
  8. ^ コーメン、トーマスH.「22.2幅優先探索」。アルゴリズムの紹介ISBN 978-81-203-4007-7OCLC1006880283 _
  9. ^ 「スタックベースのグラフ走査≠深さ優先探索」11011110.github.io 2020年6月10日取得
  10. ^ コルメン、トーマスH .; レイザーソン、チャールズE .; リベスト、ロナルドL .; スタイン、クリフォード(2001)[1990]。「22.2幅優先探索」。アルゴリズム入門(第2版)。MITPressとMcGraw-Hill。pp。531–539。ISBN 0-262-03293-7
  11. ^ ラッセル、スチュアート; Norvig、Peter(2003)[1995]。人工知能:現代的なアプローチ(第2版)。プレンティスホール。ISBN 978-0137903955
  12. ^ Coppin、B.(2004)。人工知能が照らされました。ジョーンズ&バートレットラーニング。pp。79–80。
  13. ^ アジズ、アドナン; プラカシュ、アミット(2010)。「4.グラフ上のアルゴリズム」。インタビューのアルゴリズムp。144. ISBN 978-1453792995
  14. ^ Dhulipala、Laxman; Blelloch、Guy E .; ジュリアン・シュン(2019年8月21日)。理論的に効率的な並列グラフアルゴリズムは、高速でスケーラブルです。p。17. arXiv1805.05208土井10.1145/3210377.3210414ISBN 9781450357999S2CID44126609 _

外部リンク