幅優先検索: 基礎と応用

By Fouad Sabry

幅優先検索とは

幅優先検索 (BFS) として知られる手法は、ツリー データ構造内のノードから条件を満たすノードを検索するために使用されます。 特定の基準セット。 これはツリーのベースから開始され、次の深さレベルにあるノードに進む前に、現在の深さレベルで各ノードを調査していきます。 検出されたもののまだ調査されていない子ノードを追跡するには、通常はキューの形式で追加のメモリが必要です。

メリット

(I) 次のトピックに関する洞察と検証:

第 1 章:  幅優先検索

第 2 章:  グラフ抽象データ型

第 3 章:  コンピュータ サイエンスにおけるガベージ コレクション

第 4 章:  辞書編集の幅優先検索

第 5 章:  最短経路の問題

第 6 章:  深さ優先検索

第 7 章:  双方向検索

第 8 章:  ダイクストラのアルゴリズム

第 9 章:  レベル構造

第 10 章:  反復深化深さ優先検索

(II) 幅優先検索に関する一般のよくある質問に答える。

(III) 多くの分野での幅優先検索の使用例の実例。

(IV) 「幅優先検索」テクノロジーを 360 度完全に理解するために、各業界の 266 の新興テクノロジーを簡潔に説明する 17 の付録。

本書の概要 対象者は

専門家、学部生および大学院生、愛好家、愛好家、および基本的な知識や情報を超えて、あらゆる種類の広範囲にわたる最初の検索を希望する人です。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 28, 2023

Book preview

第 1 章: 幅優先検索

幅優先検索 (BFS) と呼ばれる手法を使用して、ツリー データ構造内のノードで、特定の基準セットを満たすノードを検索します。ツリーのベースから始まり、現在の深度レベルの各ノードの調査から、次の深度レベルにあるノードに移動します。見つかったがまだ調査されていない子ノードを追跡するために、多くの場合キューの形式で追加のメモリが必要です。

たとえば、チェスのエンドゲームでは、チェスエンジンは、すべての潜在的な動きを適用して現在の位置からゲームツリーを作成し、幅優先検索を利用して白の勝利位置を特定することができます。これは、考えられるすべての動きを適用することによって行うことができます。ゲームツリーやその他の問題解決ツリーを含む暗黙的なツリーは、無制限の数のノードを持つことができます。それにもかかわらず、幅優先の検索では、少なくとも 1 つある場合は常にソリューション ノードが識別されます。

対照的に、他のノードをバックトラックして展開する前に、ノードブランチを可能な限り探索する(単純な)深さ優先検索では、無限分岐で迷子になり、ソリューションノードに到達しない可能性があります。これは、次のノードに移動する前に、ノードブランチを可能な限り拡張するためです。反復的な深化深さ優先検索は、この後者の欠点を回避することができますが、ツリーの最上部の枝を繰り返し見るという犠牲を払っています。一方、深さ優先の方法はいずれも、機能するためにこれ以上のメモリを必要としません。

開始ノード(「検索キー」とも呼ばれます)が明示的に指定され、頂点を2回たどらないように対策を講じると、幅優先検索を変更してグラフに適用できます。幅優先検索は、しばしば「検索キー」と呼ばれます。

Konrad Zuseは、BFSアルゴリズムと、1945年に博士号の(失敗した)申請でグラフの関連コンポーネントを見つけるプロセスでの使用の両方を思いつきました。

プログラミング言語プランカルキュルに関する論文、 しかし、これは1972年まで公開されませんでした。

グラフ G と G の開始頂点ルートが入力として必要です。

出力: 目標の状態。親リンクは、ルートに戻る最短距離のルートをたどります。

1 プロシージャ BFS(G, ルート) は

2 Q をキューにする

3 探索されたラベルルート

4 Q.enqueue(root)

Qが空でない間 は5

6 v := Q.dequeue()

7 vが目標の場合、

8 リターン V

G の v から w  までのすべてのエッジに対して 9  隣接エッジ(v)

10 w が探索済みとしてラベル付けされていない場合、

11 探索されたラベルw

12 w.親 := v

13 Q.エンキュー(w)

この非再帰的な方法は、深さ優先検索の非再帰的な実装と非常によく似ています。それにもかかわらず、その実装とは異なる2つの重要な側面があります。

スタックの代わりに、FIFOの原則で動作するキューを利用します。

頂点がキューから削除されるまで待機するのではなく、頂点をキューに追加する前に頂点が調査されたかどうかを確認するチェックを行います。

G がツリーの場合、この幅優先の検索方法は、アルゴリズム内のキューをスタックに置き換えることによって、深さ優先の検索戦略に変換できます。汎用グラフの場合、幅優先検索アルゴリズムの生成は、反復深さ優先検索の実装で使用されるスタックをキューに置き換えることによっても発生する可能性があります。ただし、この方法は比較的非標準です。

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

実装に応じて、ノードをコレクションに保持するか、各ノードに個別にプロパティを割り当てることによって、ノードを検査済みとしてマークできます。

頂点とノードという用語は、しばしば同じ意味で使用される場合があることに注意することが重要です。

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

幅優先検索の出力は、幅優先ツリーと呼ばれる構造です。次の図は、幅優先ツリーが実際にどのように見えるかを示しています。

以下は、ドイツの都市でフランクフルトから始まるBFS操作を実行することによって生成される可能性のある幅優先ツリーの例です。

時間の複雑さは O(|V|+|E|) 、各頂点と各エッジが最悪のシナリオで調査されるため、次のように表すことができます。

|V| は頂点の数、 は |E| グラフ内の辺の数です。

入力されているグラフのスパース度に基づいて、 O(|E|) と O(1) の間で異なる可能性がある O(|V|^{2}) ことに注意してください。

グラフ内の頂点の総数がすでにわかっている場合、 さらに、以前にキューに追加された頂点を確認するために追加のデータ構造が使用され、空間の複雑さは次のように表すことができます O(|V|) |V| 。 ここで、 は頂点の数です。

グラフ自体に必要なスペースに加えて、これが必要になります。 これは、メソッドの特定のバージョンが使用するネットワーク表現によって異なる場合があります。

直接保存するには広すぎる(または無限の)グラフを扱っている場合は、次のような別の用語を使用して幅優先検索の難しさを説明する方が実用的です。 開始点として機能するノードからd距離にあるノードを特定するには(エッジトラバーサルの数で測定)、 BFSはO(bd + 1)時間とメモリを取り、bはグラフの「分岐係数」(平均外度)です。 : 81

アルゴリズムを分析するプロセスでは、幅優先探索への入力は有限グラフであると仮定されます。このグラフは、隣接リスト、隣接行列、または任意の同等の表現として表されてもよい。一方、入力は、グラフトラバーサル技術が人工知能のコンテキストで使用される場合、無限グラフの暗黙の表現である可能性があります。この説明のコンテキストでは、検索手法は、ターゲット状態が存在すると仮定して、ターゲット状態を見つける可能性が100%ある場合に完了していると言われます。深さ優先検索は完了していませんが、幅優先検索は完了しています。幅優先検索は、暗黙的に表される無限のグラフに適用されると、最終的にターゲットの状態を特定しますが、深さ優先の検索は、目標状態を含まず、決して戻らないグラフの領域で失われる可能性があります。

グラフの頂点の列挙は、このグラフにBFSを適用した場合に考えられる出力であり、頂点が列挙に現れる順序である場合、BFS順序にあると言われます。

G=(V,E) 頂点を持つグラフとします n 。

それが の近傍集合であることを N(v) 思い出してください v 。

を の別個の要素のリスト