双向 BFS Dijkstra A*

Posted on Edited on In Disqus:

双向搜索其实也写过好多次了，但是以前一直没意识到自己写的双向 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(v) < 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) \] 也就是说 $_s(u) + _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，顺便加上了一点自己的理解。