如何使用双向BFS查找最短路径?

如何使用双向BFS查找路径" title="最短路径">最短路径?假设有一个6x6的网格。起点在(0,5)中,终点在(4,1)中。使用双向bfs的最短路径是什么?没有路径成本。而且它是无向的。

回答:

同时从源顶点和目标顶点运行两个BFS,一旦发现两个运行点共有的顶点就终止。该顶点将位于源和目标之间。

在大多数情况下,双向BFS将比简单BFS产生更好的结果。假设源与目标之间的距离为k,分支因子为B(每个顶点的平均B边平均)。

  • BFS将遍历1 + B + B^2 + ... + B^k顶点。
  • 双向BFS将遍历2 + 2B^2 + ... + 2B^(k/2)顶点。

对于大Bk,第二个显然比第一个快得多。


为简单起见,我将假设矩阵中没有障碍。这是发生了什么:

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)

以上是 如何使用双向BFS查找最短路径? 的全部内容, 来源链接: utcz.com/qa/398320.html

回到顶部