双向 BFS Dijkstra A*

双向搜索其实也写过好多次了,但是以前一直没意识到自己写的双向 Dijkstra 是假的,然后看了看网上的中文博客,前几个也都是假的,所以就写了这篇文章,不过也没人看就是了。

前置知识:BFS, Dijkstra, A*

双向 BFS 搜索

双向 BFS 其实是相当符合直觉的,从起点和终点出发,每次扩展其中一边,直到两边同时访问了一个节点就终止了,答案就是从起点到公共点再到终点的一条路径。

双向 Dijkstra 搜索

反例

以前我以为双向 Dijkstra 类似于 BFS,只要两边相遇了就可以终止了,但其实并非如此。

1
2
3
4
5
S   1   A   1   B   1   C   1   T
o-------o-------o-------o-------o
| |
+---------------+
1.5

上图是一个简单的反例,假设正反交替扩展,那么顺序就是

1
2
3
4
S -> A
T -> C
A -> B
C -> B

在四次迭代后就相遇了,然是得到的却不是最短路径。

终止条件

设图 $G$ 的起点和终点分别为 $s$ 和 $t$,边权为 $w$,搜索过程中所有点到起点和终点的距离为 $d_s$ 和 $d_t$(如果不可达则为 $\infty$)。

  • 初始化 $\mu \leftarrow \infty$
  • 在扩展起点 $s$ 那一侧时,设扩展的边是 $(u,v)$,那么令 $\mu \leftarrow \min{\mu, d_s(u)+d_t(v)+w(u,v)}$
  • 与之类似的,在扩展起点 $t$ 那一侧时,设扩展的边是 $u \Rightarrow v$,那么令 $\mu \leftarrow \min{\mu, d_t(u)+d_s(v)+w(u,v)}$

终止条件为 $top_s + top_t \ge \mu$,其中 $top_s$ 和 $top_t$ 为维护的两个最小堆的堆顶元素距离,也就是两侧即将扩展的下一个点的距离之和要大于目前的最优值。

最后答案就是 $\mu$ 所对应的那条路径。

简易证明

反证法:

  1. 设有一条 $s-t$ 之间比 $\mu$ 更短的路径 $P$。
  2. 那么肯定存在一条边 $(u, v)$ 使得 $d_s(u) < top_s$ 和 $d_t(u) < top_t$ 同时成立。(或许不那么显然,我的想法是,把 $P$ 经过的边的边权从起点到终点一个个加起来,肯定有一瞬间导致边权和从 $< top_s$ 跳变到 $\ge top_s$,那条边就是要找的符合条件的 $(u,v)$。)
  3. 然而这样的路径已经被考虑过了,所以 $P$ 不存在。(更详细一些就是,$u$ 和 $v$ 都被扩展过了,后被扩展的那个点肯定在枚举到 $(u, v)$ 这条边时把路径 $P$ 和最优值比较过了。)

A* 搜索(单向)

在理解双向 A* 之前,需要明白 A* 的正确性从何而来。

设 $\pi(u)$ 为启发式函数,就是估计的 $d(u, t)$。(其实就是 $f(u) = g(u) + h(u)$ 里的 $h(u)$),设修改过的边权 (reduced cost) $w_\pi(u, v) = w(u, v) - \pi(u) + \pi(v)$。

那么 A* 搜索等价于在这个边权修改过的图上进行 Dijkstra:

  • 对于 Dijkstra,是按照修改后的从起点出发的路径长度从小到大访问:

    $dist_\pi(s, u) = dist(s, u) - \pi(s) + \pi(u)$

  • 对于 A*,是按照 $key(u)=dist(s,u) + \pi(u)$ 从小到大的顺序访问

  • 两者就差一个常数 $\pi(s)$

当然,要保证 A* 能找到最优解,需要保证启发式函数是 feasible 的,也就是修改过的边权非负 $w_\pi(u,v) \ge 0$。

当 $\pi$ 是 feasible 且 $\pi(t)=0$ 时,$\pi(u)$ 是 $dist(u,t)$ 的下界:

  • 在修改边权后的图上,对于从 $u$ 到 $t$ 的最短路,有:
    • $dist_\pi(u, t) \ge 0$ 。由于 feasible,每条边都非负,所以累加后也非负。
    • $dist_\pi(u, t)= dist(u,t) -\pi(u) + \pi(t)=dist(u,t)-\pi(u)$。(根据修改后的边权的定义)
    • 联立可以得到 $\pi(u) \le dist(v,t)$。

双向 A* 搜索

一致性

设 $\pi_s(u)$ 和 $\pi_t(u)$ 是对 $dist(s,u)$ 和 $dist(u, t)$ 的估计。

对于同一条边 $(u,v)$ 在正反图中的 reduced cost 如果一致的话,就认为是 consistent 的:
$$
w_\pi(u,v)=w(u,v) - \pi_t(u) + \pi_t(v) = w(v,u) - \pi_s(v)+\pi_s(u) = w_\pi(v,u) \
\pi_s(u)+\pi_t(u) = \pi_s(v)+\pi_t(v)
$$
也就是说 $\pi_s(u) + \pi_t(u) = $ 常数。

通常来说,随便掏出两个 feasible 的启发式函数(比如欧氏距离,曼哈顿距离),很可能不是 consistent 的。
$$
\pi’_s(u)=\frac 12 (\pi_s(u)-\pi_t(u)+\pi_t(s)) \
\pi’_t(u)=\frac 12 (\pi_t(u)-\pi_s(u)+\pi_s(s))
$$
通过变换,获得了一个 feasible 且 consistent 的启发式函数 $\pi’$,还满足 $\pi’_s(s) =\pi’_t(t)=0$。尽管如此,相比起 $\pi$,$\pi’$ 是一个更差的估计。

终止条件

大概就是在修改过的图(也就是可以当成 Dijkstra 的图)上考虑 Dijkstra 的终止条件的证明。

正向的访问过的最长的路径(修改后) + 反向的访问过的最长的路径(修改后)≥ 最优的路径(修改后)

$\mu$ 仍旧定义为最优路径(未修改)。

  • 正向最长路径(修改后):$dist_\pi(s,u)=d_s(u) - \pi_t(s) + \pi_t(u)=top_s - \pi_t(s)$
  • 反向最长路径(修改后):$dist_\pi(u,t)=d_t(u) - \pi_s(u) + \pi_s(t)=top_t - \pi_s(t)$
  • 最优路径(修改后):$\mu -\pi_s(s) + \pi_s(t)$

那么就是
$$
[top_s - \pi_t(s)] + [top_s - \pi_s(t)] \ge [\mu -\pi_s(s) + \pi_s(t)]
$$
利用 $\pi_s(s)=0$ 和 $\pi_t(s) = \pi_s(t)$,有
$$
top_s + top_t \ge \mu + \pi_t(s)
$$

写在最后

用正确的终止条件可能会大幅影响效率,而使用错误的终止条件只会以极其微小的概率无法得到最优解。(这是在实际的地图上测试的感受,如果特意构造的数据,错误的算法必定会有错误的结果。)

参考

主要是这个 [PDF](/2020/03/31/Bidirectional-BFS-Dijkstra-A-star/Bi Directional A Star - Slides.pdf),顺便加上了一点自己的理解。