双向 BFS Dijkstra A*
双向搜索其实也写过好多次了,但是以前一直没意识到自己写的双向 Dijkstra 是假的,然后看了看网上的中文博客,前几个也都是假的,所以就写了这篇文章,不过也没人看就是了。
前置知识:BFS, Dijkstra, A*
双向 BFS 搜索
双向 BFS 其实是相当符合直觉的,从起点和终点出发,每次扩展其中一边,直到两边同时访问了一个节点就终止了,答案就是从起点到公共点再到终点的一条路径。
双向 Dijkstra 搜索
反例
以前我以为双向 Dijkstra 类似于 BFS,只要两边相遇了就可以终止了,但其实并非如此。
1 | S 1 A 1 B 1 C 1 T |
上图是一个简单的反例,假设正反交替扩展,那么顺序就是
1 | S -> A |
在四次迭代后就相遇了,然是得到的却不是最短路径。
终止条件
设图 G 的起点和终点分别为 s 和 t,边权为 w,搜索过程中所有点到起点和终点的距离为 ds 和 dt(如果不可达则为 ∞)。
- 初始化 μ ← ∞
- 在扩展起点 s 那一侧时,设扩展的边是 (u, v),那么令 μ ← min {μ, ds(u) + dt(v) + w(u, v)}
- 与之类似的,在扩展起点 t 那一侧时,设扩展的边是 u ⇒ v,那么令 μ ← min {μ, dt(u) + ds(v) + w(u, v)}
终止条件为 tops + topt ≥ μ,其中 tops 和 topt 为维护的两个最小堆的堆顶元素距离,也就是两侧即将扩展的下一个点的距离之和要大于目前的最优值。
最后答案就是 μ 所对应的那条路径。
简易证明
反证法:
- 设有一条 s − t 之间比 μ 更短的路径 P。
- 那么肯定存在一条边 (u, v) 使得 ds(u) < tops 和 dt(v) < topt 同时成立。(或许不那么显然,我的想法是,把 P 经过的边的边权从起点到终点一个个加起来,肯定有一瞬间导致边权和从 < tops 跳变到 ≥ tops,那条边就是要找的符合条件的 (u, v)。)
- 然而这样的路径已经被考虑过了,所以 P 不存在。(更详细一些就是,u 和 v 都被扩展过了,后被扩展的那个点肯定在枚举到 (u, v) 这条边时把路径 P 和最优值比较过了。)
A* 搜索(单向)
在理解双向 A* 之前,需要明白 A* 的正确性从何而来。
设 π(u) 为启发式函数,就是估计的 d(u, t)。(其实就是 f(u) = g(u) + h(u) 里的 h(u)),设修改过的边权 (reduced cost) wπ(u, v) = w(u, v) − π(u) + π(v)。
那么 A* 搜索等价于在这个边权修改过的图上进行 Dijkstra:
对于 Dijkstra,是按照修改后的从起点出发的路径长度从小到大访问:
distπ(s, u) = dist(s, u) − π(s) + π(u)
对于 A*,是按照 key(u) = dist(s, u) + π(u) 从小到大的顺序访问
两者就差一个常数 π(s)
当然,要保证 A* 能找到最优解,需要保证启发式函数是 feasible 的,也就是修改过的边权非负 wπ(u, v) ≥ 0。
当 π 是 feasible 且 π(t) = 0 时,π(u) 是 dist(u, t) 的下界:
- 在修改边权后的图上,对于从 u 到 t 的最短路,有:
- distπ(u, t) ≥ 0 。由于 feasible,每条边都非负,所以累加后也非负。
- distπ(u, t) = dist(u, t) − π(u) + π(t) = dist(u, t) − π(u)。(根据修改后的边权的定义)
- 联立可以得到 π(u) ≤ dist(v, t)。
双向 A* 搜索
一致性
设 πs(u) 和 π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 的启发式函数 π′,还满足 π′s(s) = π′t(t) = 0。尽管如此,相比起 π,π′ 是一个更差的估计。
终止条件
大概就是在修改过的图(也就是可以当成 Dijkstra 的图)上考虑 Dijkstra 的终止条件的证明。
正向的访问过的最长的路径(修改后) + 反向的访问过的最长的路径(修改后)≥ 最优的路径(修改后)
μ 仍旧定义为最优路径(未修改)。
- 正向最长路径(修改后):distπ(s, u) = ds(u) − πt(s) + πt(u) = tops − πt(s)
- 反向最长路径(修改后):distπ(u, t) = dt(u) − πs(u) + πs(t) = topt − πs(t)
- 最优路径(修改后):μ − πs(s) + πs(t)
那么就是 [tops − πt(s)] + [tops − πs(t)] ≥ [μ − πs(s) + πs(t)] 利用 πs(s) = 0 和 πt(s) = πs(t),有 tops + topt ≥ μ + πt(s)
写在最后
用正确的终止条件可能会大幅影响效率,而使用错误的终止条件只会以极其微小的概率无法得到最优解。(这是在实际的地图上测试的感受,如果特意构造的数据,错误的算法必定会有错误的结果。)
参考
主要是这个 PDF,顺便加上了一点自己的理解。