グラフ走査法は常に私を非常に魅了してきました。効果的なピアツーピア通信の実行から、GPSを使用した最寄りのレストランやカフェの検索まで、トラバーサル方式には、実際のシナリオでさまざまなアプリケーションのセットがあります。幅優先探索アルゴリズムに関するこのブログでは、グラフ走査法の背後にあるロジックについて説明し、例を使用して幅優先探索アルゴリズムの動作を理解します。
人工知能と機械学習の詳細な知識を得るには、ライブに登録できます 24時間年中無休のサポートと生涯アクセスを備えたEdurekaによる。
これが予定されているトピックのリストです このブログで取り上げられています：
グラフ走査の概要
処理のためにグラフにアクセスして探索するプロセスは、グラフ走査と呼ばれます。より具体的には、すべての頂点が1回だけ探索されるように、グラフ内の各頂点とエッジを訪問して探索することがすべてです。
簡単そうですね！しかし、落とし穴があります。
文字列をJavaで日付に変換
幅優先探索、深さ優先探索など、いくつかのグラフ走査手法があります。課題はグラフを使用することです 特定の問題を解決するのに最も適したトラバーサル手法。これにより、幅優先探索手法が実現します。
幅優先探索アルゴリズムとは何ですか？
幅優先探索アルゴリズムはグラフトラバース手法であり、ランダムな初期ノード（ソースノードまたはルートノード）を選択し、すべてのノードとそれぞれの子ノードにアクセスして探索するように、グラフのトラバースを開始します。
さらに進んで、例を使用して幅優先探索を理解する前に、グラフ走査に関連する2つの重要な用語について理解しましょう。
これをよりよく理解するには、上の図を参照してください。
例を使用して幅優先探索アルゴリズムを理解する
幅優先探索アルゴリズムは、単純なレベルベースのアプローチに従って問題を解決します。以下の二分木（グラフ）について考えてみましょう。私たちの目的は、幅優先探索アルゴリズムを使用してグラフを走査することです。
始める前に、幅優先探索アルゴリズムに関連する主要なデータ構造に精通している必要があります。
キューは、先入れ先出し方式に従う抽象的なデータ構造です（最初に挿入されたデータが最初にアクセスされます）。両端が開いており、一方の端は常にデータの挿入（エンキュー）に使用され、もう一方の端はデータの削除（デキュー）に使用されます。
次に、幅優先探索を使用してグラフをトラバースする手順を見てみましょう。
ステップ1： 空のキューを取ります。
Pythonは10進数を2進数に変換します
ステップ2： 開始ノード（ノードにアクセス）を選択し、キューに挿入します。
ステップ3： キューが空でない場合は、キューからノードを抽出し、その子ノード（ノードの探索）をキューに挿入します。
ステップ4： 抽出したノードを印刷します。
混乱しても心配しないでください。例を挙げて理解します。
以下のグラフを見てください。幅優先探索アルゴリズムを使用してグラフをトラバースします。
この例では、ノード「a」をルートノードとして割り当て、下方向への移動を開始して、上記の手順に従います。
上の画像は、幅優先探索アルゴリズムのエンドツーエンドのプロセスを示しています。これについてさらに詳しく説明します。
- ルートノードとして「a」を割り当て、それをキューに挿入します。
- キューからノード「a」を抽出し、「a」の子ノード、つまり「b」と「c」を挿入します。
- ノード「a」を出力します。
- キューは空ではなく、ノード「b」と「c」があります。 「b」はキューの最初のノードなので、それを抽出して、「b」の子ノード、つまりノード「d」と「e」を挿入しましょう。
- キューが空になるまで、これらの手順を繰り返します。すでにアクセスされているノードはキューに追加しないでください。 再び。
次に、幅優先探索アルゴリズムの擬似コードを見てみましょう。
幅優先探索アルゴリズムの擬似コード
幅優先探索アルゴリズムを実装するための擬似コードは次のとおりです。
入力：ソースノードBFS（G、s）としてのsは、Qをキューにします。 Q.enqueue（s）はsを訪問済みとしてマークします（Qは空ではありません）v = Q.dequeue（）は、グラフGのvのすべてのネイバーwについて、wが訪問されていない場合Q.enqueue（w）はwを訪問済みとしてマークします
上記のコードでは、次の手順が実行されます。
- （G、s）が入力されます。ここで、Gはグラフ、sはルートノードです。
- キュー「Q」が作成され、ソースノード「s」で初期化されます
- 「s」のすべての子ノードがマークされます
- キューから「s」を抽出し、子ノードにアクセスします
- vのすべての子ノードを処理します
- w（子ノード）をQに格納して、その子ノードにさらにアクセスします
- 「Q」が 空の
ブログを締めくくる前に、幅優先探索アルゴリズムのいくつかのアプリケーションを見てみましょう。
幅優先探索アルゴリズムのアプリケーション
幅優先探索は、驚くほど幅広いアプリケーションを備えた単純なグラフ走査法です。幅優先探索が使用されているいくつかの興味深い方法を次に示します。
Javaコードをコンパイルする方法
検索エンジンのクローラー： 幅優先探索は、Webページのインデックス作成に使用される主要なアルゴリズムの1つです。アルゴリズムはソースページからトラバースを開始し、ページに関連付けられているすべてのリンクをたどります。ここでは、各Webページがグラフのノードと見なされます。
GPSナビゲーションシステム： 幅優先探索は、GPSシステムを使用して隣接する場所を見つけるために使用される最良のアルゴリズムの1つです。
重み付けされていないグラフの最短経路と最小全域木を見つけます。 重み付けされていないグラフの場合、最短パスの背後にある考え方はエッジの数が最も少ないパスを選択することであるため、最短パスの計算は非常に簡単です。幅優先探索では、ソースノードから開始して最小数のノードをトラバースすることでこれを可能にします。同様に、スパニングツリーの場合、幅優先探索または深さ優先トラバーサルの2つの方法のいずれかを使用して、スパニングツリーを見つけることができます。
放送： ネットワーキングは、通信用のパケットと呼ばれるものを利用します。これらのパケットは、トラバーサル方式に従ってさまざまなネットワークノードに到達します。最も一般的に使用されるトラバーサル方法の1つは、幅優先探索です。これは、ネットワーク内のすべてのノード間でブロードキャストされたパケットを通信するために使用されるアルゴリズムとして使用されています。
ピアツーピアネットワーキング： 幅優先探索は、ピアツーピアネットワーク内のすべての隣接ノードを見つけるためのトラバーサル方法として使用できます。たとえば、BitTorrentはピアツーピア通信に幅優先探索を使用します。
以上が、幅優先探索アルゴリズムの動作に関するものでした。グラフを走査する方法がわかったので、もっと知りたいと思っていると思います。興味を持ってもらうための関連ブログをいくつか紹介します。
これで、このブログは終わりです。このトピックに関して質問がある場合は、下にコメントを残してください。折り返しご連絡いたします。
人工知能と機械学習の完全なコースに登録したい場合は、Edurekaが特別にキュレーションします これにより、教師あり学習、教師なし学習、自然言語処理などの手法に習熟できます。ディープラーニング、グラフィカルモデル、強化学習など、人工知能と機械学習の最新の進歩と技術的アプローチに関するトレーニングが含まれています。