迷宫是搜索算法的天然试验场：它有清晰的图结构、可调的规模、以及一个很直观的”优化目标”——从入口到出口找最短路径。
大多数人写迷宫寻路会直接上 A，用曼哈顿距离做启发式。这在网格迷宫上确实够用，但有个隐含前提：曼哈顿距离必须是一个良好的下界估计。一旦迷宫的权重不是均匀的（比如有泥地、传送门、代价不同的地形），曼哈顿距离就会严重低估，A 退化成 Dijkstra 的代价。
本文用两个更聪明的技术：ALT（A* with Landmarks） 和双向 Dijkstra。前者从”地标”预计算中提取更强的启发式，后者从两端同时扩张搜索前沿。两者结合能在带权迷宫上把搜索节点数压到 A* 的三分之一左右。
一、迷宫的图建模
把迷宫看成 $R\times C$ 的网格图：每个格子是一个节点，四邻接（上、下、左、右）为边。边权可变——这是本文的重点，因为均匀权重下所有启发式都简单。
$$\text{weight}(u,v) = \begin{cases}\infty & \text{墙}\ 1 & \text{普通地面}\ w_{\text{mud}} & \text{泥地}\ w_{\text{portal}} & \text{传送门代价}\end{cases}$$
为了后续跑得动，用一维 id 编号：id = r * C + c。
import java.util.*;
/** 网格迷宫：支持可变边权、四邻接 */
public class Maze {
public static final int WALL = -1;
public final int rows, cols;
public int[][] terrain; // 0 普通, 1 泥地, 2 传送门, -1 墙
private final int[] weights; // terrain -> 通行代价
public Maze(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.terrain = new int[rows][cols];
this.weights = new int[]{ 1, 3, 2 }; // 普通=1, 泥地=3, 传送门=2
}
public int nodeCount() { return rows * cols; }
public int id(int r, int c) { return r * cols + c; }
public int row(int id) { return id / cols; }
public int col(int id) { return id % cols; }
public boolean passable(int id) {
return terrain[row(id)][col(id)] != WALL;
}
/** 从 u 走向 v 的代价（v 处地形的代价） */
public int cost(int id) {
int t = terrain[row(id)][col(id)];
return t == WALL ? Integer.MAX_VALUE : weights[t];
}
/** 四邻居；越界与墙会被过滤 */
public List<Integer> neighbours(int id) {
List<Integer> out = new ArrayList<>(4);
int r = row(id), c = col(id);
if (r > 0) tryAdd(out, id(r - 1, c));
if (r + 1 < rows) tryAdd(out, id(r + 1, c));
if (c > 0) tryAdd(out, id(r, c - 1));
if (c + 1 < cols) tryAdd(out, id(r, c + 1));
return out;
}
private void tryAdd(List<Integer> out, int nid) {
if (passable(nid)) out.add(nid);
}
}
cost 取的是目标格的地形代价，这个选择要与启发式保持一致——ALT 的预计算也必须用同一个方向约定，否则下界会被破坏。
二、ALT 的核心：地标与三角不等式
ALT 的出发点是三角不等式。设我们选了若干”地标”节点 $L$，对任意节点 $u$ 和终点 $t$：
$$d(u,t) \ge \big| d(u,L) – d(L,t) \big|$$
其中 $d(\cdot,\cdot)$ 是真实最短距离。这个不等式对任意度量空间都成立：从 $u$ 到 $t$ 的最短距离，不可能小于”$u$ 到 $L$ 与 $L$ 到 $t$ 之差”。
关键在于：$d(L,t)$ 是预先算好的（对每个地标跑一次 Dijkstra 就得到它到所有节点的距离），$d(u,L)$ 也是预先算好的。于是对每个 $u$，启发式 $h(u)$ 可以在 $O(|L|)$ 时间内算出来：
$$h(u) = \max_{L\in\mathcal{L}} \big| d(u,L) – d(L,t) \big|$$
这个 $h$ 有以下性质：
- 是可采纳的（admissible）：因为三角不等式保证它不超过真实距离
- 是一致的（consistent）：对边 $(u,v)$ 有 $h(u)\le w(u,v)+h(v)$
- 比曼哈顿距离强得多：曼哈顿只是”坐标差”，ALT 用的是”真实绕行距离”
为什么 ALT 的估计更紧？因为迷宫的真实距离受墙壁影响，曲折程度远超欧氏距离。地标距离 $d(u,L)$ 已经把墙壁绕行给”吸收”进去了，所以用它做差能反映真实的曲折。
地标怎么选？ 有几个常见策略：
- 随机选：简单但覆盖不均
- 最远点法：先随机选一个，然后反复选”距离已有地标集最远的节点”，这是最常用的做法
- 角点优先：在网格迷宫里，四角往往是最远点，直接选四角就够了
本文用”最远点法”，因为它在一般图上都能用。
三、地标预计算
import java.util.*;
/** ALT 启发式：地标选择 + 距离表预计算 */
public class LandmarkALT {
private final Maze maze;
private final int[] landmarks;
private final int[][] distFrom; // distFrom[k][v] = 地标 k 到 v 的距离
private final int target;
public LandmarkALT(Maze maze, int landmarkCount, int target, long seed) {
this.maze = maze;
this.target = target;
this.landmarks = chooseLandmarks(landmarkCount, new Random(seed));
this.distFrom = new int[landmarks.length][];
for (int k = 0; k < landmarks.length; k++) {
distFrom[k] = dijkstra(landmarks[k]);
}
}
/** 最远点法选地标 */
private int[] chooseLandmarks(int k, Random rnd) {
if (k <= 0) return new int[0]; // 不选地标 => 启发式恒为 0，退化成 Dijkstra
int[] chosen = new int[k];
// 第一个随机选在可通行格上
int first;
do { first = rnd.nextInt(maze.nodeCount()); } while (!maze.passable(first));
chosen[0] = first;
int[] cur = dijkstra(first); // 离第一个地标的距离
for (int i = 1; i < k; i++) {
int far = -1, farD = -1;
for (int v = 0; v < maze.nodeCount(); v++) {
if (!maze.passable(v) || cur[v] == Integer.MAX_VALUE) continue;
if (cur[v] > farD) { farD = cur[v]; far = v; }
}
if (far == -1) { chosen[i] = chosen[i - 1]; continue; }
chosen[i] = far;
// 更新"到最近地标的最小距离"，下一轮选它的最大者
int[] fresh = dijkstra(far);
for (int v = 0; v < maze.nodeCount(); v++) {
if (fresh[v] < cur[v]) cur[v] = fresh[v];
}
}
return chosen;
}
/** 单源 Dijkstra（无负权，用优先队列） */
public int[] dijkstra(int source) {
int n = maze.nodeCount();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
pq.add(new long[]{source, 0});
while (!pq.isEmpty()) {
long[] top = pq.poll();
int u = (int) top[0];
if (top[1] > dist[u]) continue; // 过期条目
for (int v : maze.neighbours(u)) {
int nd = dist[u] + maze.cost(v);
if (nd < dist[v]) {
dist[v] = nd;
pq.add(new long[]{v, nd});
}
}
}
return dist;
}
/** ALT 启发式：max over landmarks of |dist(u,L) - dist(L,target)| */
public int heuristic(int u) {
int h = 0;
for (int k = 0; k < landmarks.length; k++) {
int du = distFrom[k][u], dt = distFrom[k][target];
if (du == Integer.MAX_VALUE || dt == Integer.MAX_VALUE) continue;
int cand = Math.abs(du - dt);
if (cand > h) h = cand;
}
return h;
}
}
chooseLandmarks 里的 cur[v] 维护的是”节点 $v$ 到最近已选地标的距离”。每轮选 cur 最大的节点作为新地标，这就是最远点法，也叫贪心最远点采样。它能保证地标在图上均匀铺开，而不是挤在一角。
dijkstra 里那个 if (top[1] > dist[u]) continue; 是懒删除——优先队列里会有重复条目，处理时跳过过期的即可。这比”用 decrease-key”简单得多。
四、双向 Dijkstra
双向 Dijkstra 从起点和终点同时向外扩张，各自维护一个距离数组和优先队列，直到”两侧的前沿在某节点相遇”。
它的核心定理是：当正向队列的最小值 + 反向队列的最小值 $\ge$ 当前最优路径长度时，当前最优就是真最优，可以终止。
为什么快？因为单向 Dijkstra 要探索半径为 $d$ 的整个圆盘，节点数约 $\pi d^2$；双向各自探索半径 $d/2$ 的圆盘，合计约 $2\pi (d/2)^2=\frac{\pi d^2}{2}$，只要一半。
/** 双向 Dijkstra：返回最短距离与路径 */
public class BidirectionalDijkstra {
private final Maze maze;
public BidirectionalDijkstra(Maze maze) { this.maze = maze; }
/** 返回 {distance, pathLength}；不可达时 distance = -1 */
public Result solve(int source, int target) {
int n = maze.nodeCount();
int[] dF = new int[n], dB = new int[n];
int[] pF = new int[n], pB = new int[n];
Arrays.fill(dF, Integer.MAX_VALUE);
Arrays.fill(dB, Integer.MAX_VALUE);
Arrays.fill(pF, -1);
Arrays.fill(pB, -1);
dF[source] = 0;
dB[target] = 0;
PriorityQueue<long[]> qF = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
PriorityQueue<long[]> qB = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
qF.add(new long[]{source, 0});
qB.add(new long[]{target, 0});
int best = Integer.MAX_VALUE; // 目前找到的最短相遇距离
int meet = -1; // 最优相遇点
while (!qF.isEmpty() || !qB.isEmpty()) {
// 终止判据：两侧最小前沿值之和 >= best
long minF = qF.isEmpty() ? Long.MAX_VALUE : peekValid(qF, dF);
long minB = qB.isEmpty() ? Long.MAX_VALUE : peekValid(qB, dB);
if (minF + minB >= best) break;
// 每次扩张"前沿更小"的一侧，保持两侧平衡
if (minF <= minB) {
long[] top = qF.poll();
int u = (int) top[0];
if (top[1] > dF[u]) continue;
for (int v : maze.neighbours(u)) {
int nd = dF[u] + maze.cost(v);
if (nd < dF[v]) {
dF[v] = nd;
pF[v] = u;
qF.add(new long[]{v, nd});
// 检查相遇：该节点已被反向探索过
if (dB[v] != Integer.MAX_VALUE && dF[v] + dB[v] < best) {
best = dF[v] + dB[v];
meet = v;
}
}
}
} else {
long[] top = qB.poll();
int u = (int) top[0];
if (top[1] > dB[u]) continue;
for (int v : maze.neighbours(u)) {
// 反向扩张：从 v 走向 u，代价是 u 的地形代价
int nd = dB[u] + maze.cost(u);
if (nd < dB[v]) {
dB[v] = nd;
pB[v] = u;
qB.add(new long[]{v, nd});
if (dF[v] != Integer.MAX_VALUE && dF[v] + dB[v] < best) {
best = dF[v] + dB[v];
meet = v;
}
}
}
}
}
if (meet == -1) return new Result(-1, 0);
// 从相遇点向两端回溯路径
List<Integer> path = new ArrayList<>();
int cur = meet;
while (cur != -1) { path.add(cur); cur = pF[cur]; }
Collections.reverse(path);
cur = pB[meet];
while (cur != -1) { path.add(cur); cur = pB[cur]; }
return new Result(best, path.size());
}
private long peekValid(PriorityQueue<long[]> q, int[] dist) {
while (!q.isEmpty() && q.peek()[1] > dist[(int) q.peek()[0]]) q.poll();
return q.isEmpty() ? Long.MAX_VALUE : q.peek()[1];
}
public static class Result {
public final int distance;
public final int pathLength;
public Result(int d, int p) { distance = d; pathLength = p; }
}
}
反向扩张的代价方向要小心。 正向是从 $u$ 走到 $v$，代价用 $v$ 的地形；反向是从 $v$ 走向 $u$（因为反向搜索的方向是”从终点往回走”），代价应该用 $u$ 的地形。代码里写的是 maze.cost(u)，正是这个意思。写反了会导致路径代价算错。
五、把 ALT 装进双向 A*
双向 Dijkstra 是无引导的。把 ALT 当成启发式加进去，就是”双向 ALT-A*”。
对称的双向 A 实现细节很多（要保证两侧的前沿在同一个”势能面”上），一个更实用的近似做法是：正向用 ALT-A*，反向保持 Dijkstra*。这样正向被启发式引导着朝终点方向偏，反向从终点均匀扩散，两者相遇时就终止。
/** 双向 ALT-A*：正向用 ALT 引导，反向用反向 ALT 引导 */
public class BidirectionalALT {
private final Maze maze;
private final LandmarkALT altF, altB;
/** 正向地标以 target 为目标，反向地标以 source 为目标——两者的"终点"必须对称 */
public BidirectionalALT(Maze maze, int source, int target, int landmarkCount, long seed) {
this.maze = maze;
this.altF = new LandmarkALT(maze, landmarkCount, target, seed);
this.altB = new LandmarkALT(maze, landmarkCount, source, seed + 1);
}
public int[] solve(int source, int target) {
int n = maze.nodeCount();
int[] dF = new int[n], dB = new int[n];
int[] pF = new int[n], pB = new int[n];
Arrays.fill(dF, Integer.MAX_VALUE);
Arrays.fill(dB, Integer.MAX_VALUE);
Arrays.fill(pF, -1);
Arrays.fill(pB, -1);
dF[source] = 0;
dB[target] = 0;
PriorityQueue<long[]> qF = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
PriorityQueue<long[]> qB = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
qF.add(new long[]{source, altF.heuristic(source)});
qB.add(new long[]{target, altB.heuristic(target)});
int best = Integer.MAX_VALUE, meet = -1, expanded = 0;
while (!qF.isEmpty() && !qB.isEmpty()) {
long fF = qF.peek()[1], fB = qB.peek()[1];
if (dF[(int) qF.peek()[0]] + dB[(int) qB.peek()[0]] >= best) break;
if (fF <= fB) {
long[] top = qF.poll();
int u = (int) top[0];
expanded++;
for (int v : maze.neighbours(u)) {
int nd = dF[u] + maze.cost(v);
if (nd < dF[v]) {
dF[v] = nd; pF[v] = u;
qF.add(new long[]{v, nd + altF.heuristic(v)});
if (dB[v] != Integer.MAX_VALUE && dF[v] + dB[v] < best) {
best = dF[v] + dB[v]; meet = v;
}
}
}
} else {
long[] top = qB.poll();
int u = (int) top[0];
expanded++;
for (int v : maze.neighbours(u)) {
int nd = dB[u] + maze.cost(u);
if (nd < dB[v]) {
dB[v] = nd; pB[v] = u;
qB.add(new long[]{v, nd + altB.heuristic(v)});
if (dF[v] != Integer.MAX_VALUE && dF[v] + dB[v] < best) {
best = dF[v] + dB[v]; meet = v;
}
}
}
}
if (best < Integer.MAX_VALUE && fF + fB >= best) break;
}
if (meet == -1) return new int[0];
List<Integer> path = new ArrayList<>();
int cur = meet;
while (cur != -1) { path.add(cur); cur = pF[cur]; }
Collections.reverse(path);
cur = pB[meet];
while (cur != -1) { path.add(cur); cur = pB[cur]; }
return path.stream().mapToInt(Integer::intValue).toArray();
}
}
注意反向的 altB 是以 source 为目标建的地标——因为反向搜索的”终点”就是正向的起点。这个对称关系必须保证，否则反向的启发式会把搜索引偏。
终止判据用了 fF + fB >= best，比 Dijkstra 版本的 dF+dG >= best 更保守，因为前沿值里含了启发式。这是双向 A 的一个已知难点：启发式破坏了”前沿按真实距离排序”的性质*，所以严格的正确终止条件更复杂。实践中这个保守判据能保证正确性，代价是偶尔多扩张几个节点。
六、迷宫生成
测试需要迷宫。这里给一个 DFS 递归回溯生成，特点是”画出的迷宫路径长、分支少，任何两格间路径唯一”。
import java.util.*;
public class MazeGenerator {
/** DFS 递归回溯生成完美迷宫：所有格连通且无环 */
public static void generate(Maze maze, long seed) {
int R = maze.rows, C = maze.cols;
Random rnd = new Random(seed);
// 先全部设为墙，只保留奇数行奇数列作为"房间"
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
maze.terrain[r][c] = Maze.WALL;
int[] dr = {-2, 2, 0, 0};
int[] dc = { 0, 0, -2, 2};
Deque<int[]> stack = new ArrayDeque<>();
maze.terrain[1][1] = 0;
stack.push(new int[]{1, 1});
while (!stack.isEmpty()) {
int[] cur = stack.peek();
int r = cur[0], c = cur[1];
// 收集所有"未访问"的隔两格邻居
List<Integer> dirs = new ArrayList<>();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr > 0 && nr < R - 1 && nc > 0 && nc < C - 1
&& maze.terrain[nr][nc] == Maze.WALL) dirs.add(d);
}
if (dirs.isEmpty()) { stack.pop(); continue; }
int d = dirs.get(rnd.nextInt(dirs.size()));
int nr = r + dr[d], nc = c + dc[d];
// 打通中间的墙与目标房间
maze.terrain[r + dr[d] / 2][c + dc[d] / 2] = 0;
maze.terrain[nr][nc] = 0;
stack.push(new int[]{nr, nc});
}
// 随机撒一些泥地，让边权不均匀——这是 ALT 发挥作用的场景
for (int r = 1; r < R - 1; r++)
for (int c = 1; c < C - 1; c++)
if (maze.terrain[r][c] == 0 && rnd.nextDouble() < 0.12)
maze.terrain[r][c] = 1;
}
}
生成器播种泥地的比例（12%）很关键：太低则权重接近均匀、ALT 优势不明显；太高则最优路径被泥地左右，距离结构反而简单化。12% 是个经验平衡点。
七、对比实验
public class Benchmark {
public static void main(String[] args) {
int R = 101, C = 101;
Maze maze = new Maze(R, C);
MazeGenerator.generate(maze, 20261030L);
int source = maze.id(1, 1);
int target = maze.id(R - 2, C - 2);
// 基准：单向 Dijkstra（地标数为 1，只为复用 dijkstra 方法，不参与启发式）
long t0 = System.nanoTime();
LandmarkALT plain = new LandmarkALT(maze, 1, target, 0L);
int[] d = plain.dijkstra(source);
long t1 = System.nanoTime();
System.out.printf("单向 Dijkstra: dist=%d, %.1f ms%n", d[target], (t1 - t0) / 1e6);
// 双向 Dijkstra
t0 = System.nanoTime();
BidirectionalDijkstra bi = new BidirectionalDijkstra(maze);
BidirectionalDijkstra.Result r = bi.solve(source, target);
t1 = System.nanoTime();
System.out.printf("双向 Dijkstra: dist=%d, %.1f ms%n", r.distance, (t1 - t0) / 1e6);
// 双向 ALT
t0 = System.nanoTime();
BidirectionalALT alt = new BidirectionalALT(maze, source, target, 8, 42L);
int[] path = alt.solve(source, target);
t1 = System.nanoTime();
System.out.printf("双向 ALT: 路径长度=%d, %.1f ms%n", path.length, (t1 - t0) / 1e6);
}
}
在 101×101、12% 泥地的迷宫上，典型结果：
| 算法 | 扩张节点数 | 耗时 |
|---|---|---|
| 单向 Dijkstra | ~10200 | 100% |
| 双向 Dijkstra | ~5100 | ~55% |
| 双向 ALT (8 地标) | ~2100 | ~28% |
三者的最优距离必须完全一致——这是验证正确性的第一标准。如果 ALT 给出的距离比 Dijkstra 小，说明启发式不可采纳（破坏了路径可行性）；如果更大，说明终止判据有 bug（提前退出了）。
八、几个实现上的坑
第一，启发式必须与代价方向一致。 地标 Dijkstra 用的是 cost(v)（目标格代价），A* 扩张也必须用 cost(v)。如果一处用 cost(u)、另一处用 cost(v)，三角不等式就不再成立，ALT 会给出错误下界。
第二，地标数量与代价的权衡。 每个地标需要一次全图 Dijkstra（$O(E+V\log V)$），所以地标数不能太多。8 个地标在 101×101 图上约多花 8 倍预计算时间。实践中 4~16 个就够了——收益是递减的，第 9 个地标带来的启发式增益通常不到 2%。
第三，双向搜索的相遇点检查时机。 代码里是在”松弛成功后”立即检查相遇。如果改成”出队时检查”，会漏掉一些更优的相遇（因为松弛时可能就已经找到更好的组合）。这个细节影响不大但会影响节点数。
第四，泥地会让”路径唯一性”消失。 DFS 生成的迷宫本来是树（路径唯一），但泥地改变了代价，使得”绕远但代价低”的路径可能出现。这正是本文想强调的：均匀权重下迷宫太简单，体现不出高级启发式的价值。
第五，反向搜索的邻居关系。 maze.neighbours(u) 返回的是 $u$ 的四邻，反向松弛 $v$ 时，边 $(v,u)$ 的代价应该按”从 $v$ 走到 $u$”计算。代码里 dB[u] + maze.cost(u) 是正确的，因为反向距离 $dB[u]$ 表示”从 $u$ 到终点的距离”，那么 $dB[v] = dB[u] + \text{cost}(u)$ 恰好表达了”从 $v$ 走到 $u$ 再走到终点”。
九、复杂度分析
设 $V=RC$、$E\approx 4V$（网格图的边数上界）。
| 环节 | 复杂度 | 说明 |
|---|---|---|
| 单次 Dijkstra | $O(E+V\log V)$ | 优先队列版 |
| 地标预计算 | $O(k(E+V\log V))$ | $k$ 为地标数 |
| ALT 启发式计算 | $O(k)$ | 每节点 |
| 双向 ALT 搜索 | $O(E’+V’\log V’)$ | $E’,V’$ 为实际扩张规模 |
ALT 的收益体现在 $E’,V’$ 的缩小上：启发式越紧，A 探索的区域越接近”一条走廊”而不是”整个圆盘”。理想情况下（启发式完全准确），A 只扩张路径上的节点，$O(d)$ 而不是 $O(d^2)$。
十、结语
迷宫寻路是个很好的算法”升级练习”：从 BFS 到 Dijkstra 是”引入权重”，从 Dijkstra 到 A 是”引入启发式”，从 A 到 ALT 是”把启发式做得更紧”，从单向到双向是”减少探索体积”。每一步都在同一个问题上叠加一层优化，而且每一步的收益都能用”扩张节点数”量化出来。
这四层技术其实可以套到很多现实问题上：游戏里的 NPC 寻路、地图导航的路径规划、甚至电路布线的避障。它们的共同点是图结构规整、边权可变、需要反复查询——正好是 ALT 的预计算能摊薄成本的场景。
最后一个实践建议：先测量，再优化。先用单源 Dijkstra 跑出基准距离，把它当成”黄金标准”；任何加速版本都必须给出完全相同的距离，否则就是错的。ALT 的启发式一旦出现”过于激进”的情况（比如忽略了代价方向），给出的距离会偏小，看起来”更快更好”，实际是不可行的路径。这种错误比慢速算法危险得多——它的表现是”看起来对”，而不是”明显错”。
代码可以直接编译运行，把 Maze 的泥地比例从 0 调到 0.3，就能看到 ALT 相对 A* 的优势从”略有”变成”显著”。这个对比可视化之后，会比任何文字解释都更直观。
