地图导航算法 #02：双向搜索

双向搜索同时从起点和终点向中间展开，两个搜索前沿相遇时即可合并路径；理论上将搜索空间从半径 r 的球体压缩为两个半径 r/2 的球体，节点展开量减少约 50%，是 Contraction Hierarchies 查询阶段的核心机制。

相关文章：A* 算法 · Contraction Hierarchies

目录

核心思想

单向搜索以起点为圆心，半径 r 扩展，搜索空间 ∝ r²（二维）或 r³（三维）。

双向搜索以起点和终点各扩展半径 r/2，两个球体相遇：

搜索空间（简化为二维圆面积）：

  单向：π × r²          双向：2 × π × (r/2)² = π × r² / 2

  理论节点减少：50%

实际路网上加速比通常在 2x～4x，配合 A* 启发函数可进一步提升。

双向 Dijkstra

数据结构

维护两套独立的状态：

后向搜索在反向图上运行（原图所有边反转）。

算法流程

初始化：
  distF[S] = 0,  distB[G] = 0
  fwdQ = {S},    bwdQ = {G}
  best = ∞,  meetNode = -1

交替展开（每轮选 f 值更小的队列展开一步）：
  从 fwdQ 取出 u（distF 最小）：
    for 每条边 u→v（正向图）：
      if distF[u] + w(u,v) < distF[v]:
        更新 distF[v]，入队
    if v ∈ closedB:                  ← v 已被后向探索
      candidate = distF[v] + distB[v]
      if candidate < best:
        best = candidate, meetNode = v

  从 bwdQ 取出 u（distB 最小）：
    （对称处理反向图）

终止条件（见下节）：
  当 distF[u] + distB[u] ≥ best 时停止

路径重建

从 meetNode 向前回溯 parentF → 得到 S→meetNode 的路径
从 meetNode 向后回溯 parentB → 得到 meetNode→G 的路径
拼接两段路径

双向 A*

双向 A* 比双向 Dijkstra 更复杂，因为两个方向的启发函数需要保持一致性。

启发函数修正（Pohl 修正）

前向启发函数 hF(v) 估计 v→G 的代价，后向启发函数 hB(v) 估计 v→S 的代价。

直接使用两个独立启发函数会导致搜索前沿不对称，可能错过最优解。Pohl（1971）提出修正：

p(v) = [ hF(v) - hB(v) ] / 2

前向优先级：f_fwd(v) = distF[v] + p(v) + C/2
后向优先级：f_bwd(v) = distB[v] - p(v) + C/2

C = hF(S)（起点到终点的初始启发值，常数）

实践中，地图导航常用双向 A* 近似版本：直接用欧式距离作为两个方向的启发函数，接受极少概率的次优解，换取实现简洁性。

终止条件的陷阱

错误的终止条件

// ❌ 错误：两个前沿有公共节点就停止
if (closedF.contains(u) && closedB.contains(u)) return;

反例：

S ──1── A ──100── G
S ──50── B ──1── G

前向展开 S→A（代价 1），后向展开 G→A（代价 100），A 进入两个 closed 集合。 若此时停止，返回路径 S→A→G（代价 101），但最优路径是 S→B→G（代价 51）。

正确的终止条件

维护全局最优值 best。当两个队首的代价之和 ≥ best 时，才能安全停止：

// ✅ 正确：队首 d_fwd + d_bwd ≥ 当前最优才终止
double fwdTop = fwdQ.peek().dist;
double bwdTop = bwdQ.peek().dist;
if (fwdTop + bwdTop >= best) break;

每次从任一方向松弛到节点 v 时，若 v 已被另一方向探索，更新 best：

if (closedB.contains(v)) {
    best = Math.min(best, distF[v] + distB[v]);
}

Java 实现

import java.util.*;

public class BidirectionalDijkstra {

    record State(int node, double dist) implements Comparable<State> {
        public int compareTo(State o) { return Double.compare(dist, o.dist); }
    }

    /**
     * @param fwd  正向邻接表：fwd[u] = [(v, weight)]
     * @param bwd  反向邻接表：bwd[v] = [(u, weight)]（即原图边反转）
     */
    public static double search(List<double[]>[] fwd, List<double[]>[] bwd, int S, int G) {
        int n = fwd.length;
        double[] dF = new double[n], dB = new double[n];
        Arrays.fill(dF, Double.MAX_VALUE);
        Arrays.fill(dB, Double.MAX_VALUE);
        boolean[] closedF = new boolean[n], closedB = new boolean[n];

        dF[S] = 0; dB[G] = 0;
        PriorityQueue<State> qF = new PriorityQueue<>(), qB = new PriorityQueue<>();
        qF.offer(new State(S, 0)); qB.offer(new State(G, 0));

        double best = Double.MAX_VALUE;

        while (!qF.isEmpty() || !qB.isEmpty()) {
            // 终止条件：两个队首之和 >= 当前最优
            double topF = qF.isEmpty() ? Double.MAX_VALUE : qF.peek().dist;
            double topB = qB.isEmpty() ? Double.MAX_VALUE : qB.peek().dist;
            if (topF + topB >= best) break;

            // 选代价更小的方向展开一步
            if (topF <= topB) {
                State cur = qF.poll();
                if (closedF[cur.node]) continue;
                closedF[cur.node] = true;
                for (double[] e : fwd[cur.node]) {
                    int v = (int)e[0]; double w = e[1];
                    if (dF[cur.node] + w < dF[v]) {
                        dF[v] = dF[cur.node] + w;
                        qF.offer(new State(v, dF[v]));
                        if (closedB[v])
                            best = Math.min(best, dF[v] + dB[v]);  // 更新最优
                    }
                }
            } else {
                State cur = qB.poll();
                if (closedB[cur.node]) continue;
                closedB[cur.node] = true;
                for (double[] e : bwd[cur.node]) {
                    int v = (int)e[0]; double w = e[1];
                    if (dB[cur.node] + w < dB[v]) {
                        dB[v] = dB[cur.node] + w;
                        qB.offer(new State(v, dB[v]));
                        if (closedF[v])
                            best = Math.min(best, dF[v] + dB[v]);
                    }
                }
            }
        }
        return best == Double.MAX_VALUE ? -1 : best;
    }
}

性能与局限

实际加速比

实测低于理论值，原因：路网并非均匀球体，城郊道路密度差异导致两个前沿扩展速度不对称。

局限

• 仍需 O(√N) 量级的节点展开：对亿级路网仍需数十毫秒，不满足实时导航要求
• 反向图需要预先建立，占用额外内存
• 双向 A* 实现复杂，启发函数一致性难以保证

在 Contraction Hierarchies 中的角色

CH 查询阶段就是一种特殊的双向搜索——但只在预处理好的层级图上运行，搜索空间被压缩到数千个节点，单次查询 < 1ms。双向搜索是 CH 的内核，而不是替代品。

详见 Contraction Hierarchies。

参考资料

参考资料

• Pohl, Bi-directional search (1971) — 双向 A* 启发函数修正
• A* 算法（单向启发式搜索基础）
• Contraction Hierarchies（工业级导航算法，双向搜索的升级版）