18

最短パスを見つけるために双方向 BFS をどのように使用しますか? 6x6 グリッドがあるとしましょう。始点は (0,5) にあり、終点は (4,1) にあります。双方向 bfs を使用した最短パスは何ですか? パスコストはありません。しかも無向です。

4

1 に答える 1

52

双方向 BFS はどのように機能しますか?

ソース頂点とターゲット頂点の両方から 2 つの BFS を同時に実行し、両方の実行に共通する頂点が検出されると終了します。この頂点は、ソースとターゲットの中間になります。

なぜBFSよりも優れているのですか?

ほとんどの場合、双方向 BFS は単純な BFS よりもはるかに優れた結果をもたらします。ソースとターゲットの間の距離がkであり、分岐係数がB(すべての頂点が平均して B エッジを持っている) であると仮定します。

  • 1 + B + B^2 + ... + B^kBFS は頂点をトラバースします。
  • 双方向 BFS は2 + 2B^2 + ... + 2B^(k/2)頂点を横断します。

Bとが大きいk場合、2 番目の方が明らかに 1 番目よりもはるかに高速です。

あなたの場合：

簡単にするために、マトリックスに障害物はないと仮定します。何が起こるかは次のとおりです。

iteration 0 (init):
front1 = { (0,5) }
front2 = { (4,1) }

iteration 1: 
front1 = { (0,4), (1,5) }
front2 = { (4,0), (4,2), (3,1), (5,1) }

iteration 2:
front1 = { (0,3), (1,4), (2,5) }
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) }

iteration 3:
front1 = { (0,2), (1,3), (2,4), (3,5) }
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), }

iteration 4:
front1 = { (0,1), (1,2), .... }
front2 = { (1,2) , .... }

ここで、前線が (1,2) で交差し、ソース頂点とターゲット頂点からそこにたどり着くまでの経路を発見しました。

path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2)
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2)

完全なパスを得るには、パス 2 を逆にしてパス 1 に追加する必要があります (もちろん、共通の交差する頂点の 1 つを削除します)。

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)
于 2012-11-01T14:30:39.183 に答える