如何使用双向 BFS 找到最短路径？假设有一个 6x6 的网格。 起点在 (0,5) 中，终点在 (4,1) 中。使用双向 bfs 的最短路径是什么？没有路径成本。而且它是无向的。
最佳答案
双向 BFS 如何工作？
同时从源顶点和目标顶点运行两个 BFS，一旦发现两个运行的公共(public)顶点就终止。该顶点将位于源和目标之间。
为什么比 BFS 好？
在大多数情况下，双向 BFS 会产生比简单 BFS 更好的结果。假设源和目标之间的距离为k，分支因子为B(每个顶点平均有B条边)。
- BFS 将遍历
1 + B + B^2 + ... + B^k个顶点。 - 双向 BFS 将遍历
2 + 2B^2 + ... + 2B^(k/2)个顶点。
对于大的 B 和 k，第二个显然比第一个快得多。
在您的情况下:
为简单起见，我假设矩阵中没有障碍物。这是发生的事情:
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(当然要删除一个常见的相交顶点)，从而为我们提供完整的路径:
(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)
关于algorithm - 如何使用双向 BFS 找到最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10995699/