如何使用双向BFS查找最短路径? [英] How do you use a Bidirectional BFS to find the shortest path?

查看:723
本文介绍了如何使用双向BFS查找最短路径?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

How do you use a Bidirectional BFS to find the shortest path? Let's say there is a 6x6 grid. The start point is in (0,5) and the end point is in (4,1). What is the shortest path using bidirectional bfs? There are no path costs. And it is undirected.

推荐答案

双向BFS如何工作?

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

Simultaneously run two BFS's from both source and target vertices, terminating once a vertex common to both runs is discovered. This vertex will be halfway between the source and the target.

为什么它比BFS更好?

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

Bi-directional BFS will yield much better results than simple BFS in most cases. Assume the distance between source and target is k, and the branching factor is B (every vertex has on average B edges).


  • BFS将遍历 1 + B + B ^ 2 + ... + B ^ k 顶点。

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

  • BFS will traverse 1 + B + B^2 + ... + B^k vertices.
  • Bi-directional BFS will traverse 2 + 2B^2 + ... + 2B^(k/2) vertices.

对于大型 B k ,第二个显然比第一个要快得多。

For large B and k, the second is obviously much faster the the first.

对于您的情况:

为简单起见,我假设矩阵中没有障碍。这就是发生的情况:

For simplicity I am going to assume that there are no obstacles in the matrix. Here is what happens:

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)处相交,以及从源顶点和目标顶点到达那里的路径:

Now, we have discovered that the fronts intersect at (1,2), together with the paths taken to get there from the source and target vertices:

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

我们现在只需要反转路径2并将其附加到路径1中(删除当然是常见的相交顶点之一),为我们提供了完整的路径:

We now just need to reverse path 2 and append it to path 1 (removing one of the common intersecting vertices of course), to give us our complete path:

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)

这篇关于如何使用双向BFS查找最短路径?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆