algorithm - 誰かが幅優先探索を説明できますか?

Question

誰かが以下の種類の問題を解決するための幅優先探索を説明できますか

4 と 7 の間のすべてのパスを見つける必要があります

Answer 1

開始ノードに隣接するすべてのノードを確認します。次に、それらに隣接するすべてのノードを調べます (既に見たノードには戻りません)。満足のいくノードが見つかるか、ノードがなくなるまで繰り返します。

あなたが示した種類の問題については、上記のプロセスを使用して一連のパスを作成し、目的の宛先ノードに到達したパスを終了します。グラフが使い果たされると、そのように終了した一連のパスがソリューション セットになります。

Answer 2

幅優先検索 (BFS) は、より深いレベルに進む前に、開始ノードの直接の子をすべて処理することを意味します。BFS は、処理が必要なノードのリストを格納するキューを使用して実装されます。

開始ノードをキューに追加して、アルゴリズムを開始します。次に、キューに処理するものがなくなるまでアルゴリズムを実行し続けます。

要素をキューからデキューすると、その要素がアクティブ ノードになります。アクティブなノードを処理しているときは、そのすべての子をキューの後ろに追加します。空のキューがある場合は、アルゴリズムを終了します。

ツリーではなくグラフを扱っているため、ループに入らないように、処理されたノードのリストを保存する必要があります。

ノード 7 に到達すると、一致するパスが得られ、その再帰パスに対する BFS の実行を停止できます。つまり、その子をキューに追加しないだけです。ループを回避し、訪問した正確なパスを知るには、再帰的な BFS 呼び出しを行うときに、既に訪問したノードを渡します。

Answer 3

他のサイトへのリンクを含む Web サイトと考えてください。A をルート ノードまたは開始 Web サイトとします。

A は開始ページ (レイヤー 1)
AA、AB、AC へのリンク (レイヤー 2)
AA から AAA、AAB、AAC へのリンク (レイヤー 3)
AB から ABA、ABB、ABC へのリンク (レイヤー 3)
AC から ACA、ACB、ACC へのリンク (レイヤー 3)

これはわずか 3 層の深さです。一度に 1 つのレイヤーを検索します。したがって、この場合、レイヤー A から開始します。それが一致しない場合は、次のレイヤー AA、AB、および AC に進みます。これらの Web サイトのいずれも探しているものでない場合は、リンクをたどって次の層に進みます。つまり、一度に 1 つのレイヤーを確認します。

深さ優先検索 (その補足) では、A から AA から AAA に進みます。言い換えれば、WIDE になる前に DEEP になります。

Answer 4

ルート ノードに接続されている各ノードをテストします。次に、前のノードに接続されている各ノードをテストします。答えが見つかるまで、これを繰り返します。

基本的に、各反復は、ルート ノードから同じ距離にあるノードをテストします。

Answer 5

始める

4;

4,2;

4,2,1; 4,2,3; 4,2,5;

4,2,1;(失敗) 4,2,3,6; 4,2,5,6; 4,2,5,11;

4,2,3,6,7;(パス) 4,2,3,6,8; 4,2,5,6,7;(パス) 4,2,5,6,8; 4,2,5,11,12;

4,2,3,6,8,9; 4,2,3,6,8,10; 4,2,5,6,8,9; 4,2,5,6,8,10; 4,2,5,11,12;(失敗)

4,2,3,6,8,9;(失敗) 4,2,3,6,8,10;(失敗) 4,2,5,6,8,9;(失敗) 4,2,5 ,6,8,10;(失敗)

終わり