寻路算法完全拆解：从 BFS、Dijkstra 到 A* 与 JPS

这篇文章是一份“算法论文式”的寻路入门教程：先用生活里的例子建立直觉，再把地图严格地变成数学对象，然后一个方法一个方法地拆开——每个方法都有核心思想、伪代码、一张可以动手验算的网格、公式推导、复杂度分析，最后统一对比它们的优劣与适用场景。全文的阅读顺序严格由浅入深：你不需要任何预备知识，唯一的要求是愿意跟着例子一步一步算。

如果读到这里你还没见过我做的寻路可视化，可以先打开寻路算法可视化实验室，一边看动画一边对照本文；文末会专门教你怎么用它做实验。

1 引言：为什么需要“寻路”

想象三个场景。第一个场景：外卖骑手要在城市里从商家送餐到顾客家，路上有单行道、堵车路段和修路围挡，他想走“时间最短”的路线。第二个场景：你在玩《我的世界》或者《星际争霸》，点了一下地图另一头，游戏角色需要绕过山脉和河流自己走过去，还不能卡在墙角。第三个场景：手机地图导航让你在早高峰避开拥堵，走了一条“距离不是最短、但时间最短”的路。

这三个场景的共同点是：从一个位置到另一个位置，找到一条路，最好还是一条“好”的路。听起来简单，难在哪里？难点有三个。

第一，地图很大。一张 32×22 的格子地图就有 704 个格子；真实地图的交叉路口数以万计。把每条可能的路线都列出来，数量会爆炸式增长，根本列不完。“爆炸式增长”到底有多可怕，第 3 节会用具体数字解释。

第二，“好”的标准不止一个。有时候要“步数最少”，有时候要“时间最短”，有时候要“尽量少转弯”，还有时候“第一快找到一条路就行，不要求最短”。不同标准对应不同方法，这正是本文要讲清楚的。

第三，搜索过程要“聪明地偷懒”。一个优秀的寻路方法不能把地图上每个格子都看一遍，而应该把注意力集中在“最有可能通往终点”的方向上。怎么定义“最有可能”，是后面所有“看目标”类方法的核心问题。

下面把问题正式写出来：给定一张地图，起点 $S$，终点 $G$，我们要输出一条从 $S$ 到 $G$ 的路径；如果存在多条，则尽量让路径“代价”最小。在动手之前，必须先回答一个更基础的问题：地图怎么变成计算机能算的数学对象？

2 从地图到图：先把世界“翻译”成数学

2.1 顶点、边与权重

计算机不懂“马路”和“沼泽”，它只懂数字和关系。于是我们把地图抽象成一张图（graph），记作：

$$G=(V,E),\qquad w:E\to\mathbb{R}_{\ge 0}$$

其中 $V$ 是顶点（vertex）的集合，$E$ 是边（edge）的集合，$w$ 是给每条边贴上的非负数字，叫做权重（weight）。把地图翻译成图的规则很简单：

• 每个可以站立的格子或路口，是一个顶点；
• 两个相邻且都可以通过的格子之间，连一条边；
• 边上的权重表示“走这一步要花多少代价”：普通路是 1，沼泽是 3，山路是 5，墙没有边。

于是“一条路”就变成了“一串首尾相接的边”，它的总代价是每条边的权重相加：

$$C(P)=\sum_{i=0}^{k-1} w(v_i,v_{i+1})$$

其中 $P=(v_0,v_1,\dots,v_k)$ 是一条从 $v_0$ 到 $v_k$ 的路径。寻路问题可以重新表述成：在所有从 $S$ 到 $G$ 的路径里，找一条让 $C(P)$ 最小的路径。计算机科学里这叫“最短路问题”，本文所有方法本质上都在解这个问题，只是各自用了不同的策略。

对于格子地图，最常用的建模方式是网格图：把地图切成一行一行的格子，每个格子就是一个顶点。比如下面这张 5×5 的地图，第 0 行第 2 列、第 1 行第 2 列、第 2 行第 2 列是墙（用 X 表示），其余格子都能走：

列    0   1   2   3   4
行 0  S   .   X   .   .
行 1  .   .   X   .   .
行 2  .   .   X   .   .
行 3  .   .   .   .   .
行 4  .   .   .   .   G

起点 S 在第 0 行第 0 列，终点 G 在第 4 行第 4 列。后面好几节都会在这张图上逐步验算，我把它命名为网格 A。整张图有 22 个可通行顶点和若干条边；注意，被墙隔开的两个格子之间没有边。

网格化之后，墙所在的格子根本不是顶点，自然也不会有任何边穿过它；这正是“墙没有边”这句话的来历。

2.2 四方向移动与八方向移动

网格上“相邻”有两种常见定义：

• 四方向（4-directional）：只能上下左右走，每个格子最多 4 个邻居，每走一步代价固定为 1；
• 八方向（8-directional）：还能斜着走，每个格子最多 8 个邻居；直线一步代价 1，斜线一步代价 $\sqrt{2}\approx1.414$，因为斜线的几何长度更长。

斜着走有一个重要的限制：不能“穿墙角”。也就是说，从 $(r,c)$ 斜走到 $(r+1,c+1)$ 时，$(r+1,c)$ 和 $(r,c+1)$ 这两个格子必须至少有一个可以通行，否则角色就会从墙角的尖上挤过去，看起来像穿模。可视化实验室用的正是这条规则。

2.3 三种距离公式：启发式的“原料”

在做搜索之前，我们常常想知道“终点大概还有多远”。这个“大概有多远”用一个函数 $h(n)$ 表示，$n$ 是当前格子，$h$ 叫做启发式函数（heuristic function）：它只根据坐标估算距离，完全不管墙。三种最常见的距离如下。

曼哈顿距离，适合四方向移动，像城市里只能沿街道走：

$$h_{\mathrm{Manhattan}}(n)=|r_n-r_g|+|c_n-c_g|$$

欧氏距离，适合可以任意方向直走的场景，是两点间的直线长度：

$$h_{\mathrm{Euclidean}}(n)=\sqrt{(r_n-r_g)^2+(c_n-c_g)^2}$$

八格距离（也叫 octile 距离），适合八方向移动，因为对角一步是 $\sqrt{2}$：

$$h_{\mathrm{octile}}(n)=\sqrt{2}\cdot\min(dr,dc)+|\;dr-dc\;|$$

其中 $dr=|r_n-r_g|$，$dc=|c_n-c_g|$。如果只用四方向移动，也可以使用更简单的切比雪夫距离 $h(n)=\max(dr,dc)$，它代表“至少要横着走这么多、竖着走这么多，所以步数不少于两者中的较大者”。

以网格 A 为例：起点 $(0,0)$ 到终点 $(4,4)$，$dr=4$，$dc=4$。三种估计分别是：

$$h_M=4+4=8,\qquad h_E=\sqrt{4^2+4^2}=\sqrt{32}\approx5.657,\qquad h_O=4\sqrt{2}\approx5.657$$

曼哈顿说“至少 8 步”，因为四方向移动最短路径确实恰好 8 步；欧氏说“直线距离 5.657”；八格距离说“八方向下至少 5.657”。注意，这三种都只是“下界式估计”：墙只会让真实距离更远，不会更近。 这个“估计不大于真实距离”的性质非常重要，后面讲到“看目标”的搜索方法时会正式定义它，并用它证明一种方法为什么能保证找到最短路径。

3 搜索的通用框架：一颗不断长大的树

有了图，怎么“找路”？所有寻路方法共享同一个骨架：从起点出发，不断“展开（expand）”当前顶点，把它的邻居放进一个待办集合，再从中挑一个继续展开，直到到达终点或没有顶点可展开。

展开过程天然形成一棵搜索树（search tree）。根是起点 $S$；每个顶点被展开时，它的每个未访问邻居都成为它的孩子；一条从根到某个节点的路径，恰好对应地图上的一条真实路线。

方法内部需要维护两个集合：

• 开放表（open / frontier）：已经发现、但还没展开的顶点，是“待办清单”；
• 关闭表（closed）：已经展开过的顶点，是“干过活的记录”，防止重复劳动。

“先展开谁”决定了方法的性格。下面先认识三个基础工具，它们是“待办清单”的三种排队方式。

3.1 队列、栈、优先队列：三种“待办清单”

队列（queue）：像食堂排队，先来的人先打饭，后来的人排在队尾。计算机术语叫“先进先出”（First In, First Out，简称 FIFO）。如果你用队列管理开放表，那么最先被发现的顶点会最先被展开。

栈（stack）：像叠盘子，最后放上去的盘子最先拿走；也像编辑器里的“撤销”，最后一步操作最先被撤销。术语叫“后进先出”（Last In, First Out，简称 LIFO）。如果你用栈管理开放表，那么最新被发现的顶点会最先被展开。

优先队列（priority queue）：像医院急诊室，谁的情况更紧急（数字更小）谁先看，而不是按到达顺序。每个元素带一个数字，每次取出数字最小的。计算机里常用一种叫“堆（heap）”的结构实现优先队列，放一个元素或取一个元素大约只需要 $\log_2 n$ 次比较——$n$ 是队列里元素的数量，而 $\log_2 n$ 的意思是“2 要自乘多少次才能达到 n”。举个例子：$n=1000$ 时 $\log_2 1000\approx10$，所以从 1000 个候选中取最小值的成本大约是 10 次比较，而不是 1000 次。这个“对数”概念后面算复杂度时会反复用到。

3.2 大 O：怎么衡量“快不快”

假设地图上有 $V$ 个顶点、$E$ 条边（$V$ 来自 vertex，$E$ 来自 edge）。我们想知道一个方法大约要做多少次操作。精确计算太麻烦，也没必要——我们只需要知道“当地图变大时，操作次数按什么速度增长”。这就是大 O 记号（Big-O notation）。

用具体数字理解：如果地图规模翻倍，一个“$O(n)$”的方法，操作次数大约也翻倍；一个“$O(n^2)$”的方法，操作次数大约变成原来的 4 倍；一个“$O(2^n)$”的方法，操作次数会变成天文数字。举个例子，$n=30$ 时：

$$2^{30}=1073741824$$

十亿次操作！这就是第 1 节说的“爆炸式增长”：如果把每条路线都列出来，哪怕只有 30 步长的路线，数量也可能超过十亿条。所以寻路方法必须避免“把全部路线都列一遍”。

读大 O 的方法很简单：只看“最大的那一项”，丢掉常数和较小的项。比如“$3V+5E$ 次操作”写成 $O(V+E)$；而“$E$ 次操作乘以每次 $\log_2 V$ 次比较”写成 $O(E\log V)$。

3.3 评价一个寻路方法，看四个指标

1. 完备性（completeness）：只要存在路径，它是否保证能找到一条？
2. 最优性（optimality）：找到的是否一定是最短（代价最小）的路径？
3. 时间复杂度（time complexity）：大约要展开多少个顶点、做多少次操作？
4. 空间复杂度（space complexity）：最多要同时记住多少个顶点？

这四个指标就像考试的四门科目：有的方法“语文好但数学差”，有的“门门均衡但偏慢”。后面每一节我们都会给每个方法打分。

还有一个常用概念叫分支因子（branching factor），记作 $b$：平均每个顶点有多少个可用的邻居。四方向移动的网格里 $b\le4$，八方向 $b\le8$。如果每一步都有 $b$ 个选择，走 $d$ 步就可能有大约 $b^d$ 条路线：

$$b^d=\underbrace{b\times b\times\cdots\times b}_{d\text{ 个}}$$

这就是“指数爆炸”的数学来源：$b=4$、$d=15$ 时，$4^{15}=1073741824$，又是十亿级别。所以聪明的方法必须尽量不去展开那些“明显没希望”的顶点。

4 BFS：像洪水一样一层层扩散

4.1 核心思想

想象往水池里扔一块石头，水波一圈一圈往外扩散：先到达离石头 1 米的地方，再到达 2 米、3 米……每圈都是一个“层”。广度优先搜索（Breadth-First Search，简称 BFS） 就是这么扩散的：从起点开始，先展开离起点 1 步的所有顶点，再展开离起点 2 步的所有顶点，依此类推。

另一个比喻是“朋友传话”：你有一条消息要传给一个住在很多街区外的人。你先把它告诉所有邻居（1 步内的人），他们再告诉他们的邻居（2 步内的人）……谁先收到消息，谁就是“最快能收到”的人。

BFS 管理开放表用的正是第 3 节讲的队列：先来先服务。因为先发现的一定是更近的，所以展开顺序天然按“离起点越来越远”排列。

4.2 伪代码

BFS(图 G, 起点 S, 终点 G):
  队列 = [S]
  记录 visited = {S}          # 防止重复
  记录 parent = {S: 无}        # 记下“从哪里来”，最后回溯路径
  当 队列 非空:
    u = 队列.pop()             # 从队头取出（先进先出）
    如果 u == G: 根据 parent 回溯，返回路径
    对 u 的每个邻居 v:
      如果 v 不在 visited:
        visited.add(v)
        parent[v] = u
        队列.append(v)         # 放到队尾
  返回“无路可走”

这里的 parent 就像一个“路标”：每个顶点都记着自己是从哪个顶点走过来的，找到终点后一路回溯，就能倒着拼出整条路径。

4.3 在网格 A 上逐步验算

网格 A 起点是 $(0,0)$，终点是 $(4,4)$，三面墙在第 2 列。四方向移动，每步代价 1。我用脚本逐层展开了所有顶点，得到下面的访问顺序。编号就是它被展开的顺序，L 表示“离起点多少步”（第几层）：

编号	顶点	层数	编号	顶点	层数
1	(0,0)	0	10	(4,1)	5
2	(1,0)	1	11	(3,2)	5
3	(0,1)	1	12	(4,2)	6
4	(2,0)	2	13	(3,3)	6
5	(1,1)	2	14	(4,3)	7
6	(3,0)	3	15	(2,3)	7
7	(2,1)	3	16	(3,4)	7
8	(4,0)	4	17	(4,4)	8
9	(3,1)	4

注意一个有趣的细节：终点 $(4,4)$ 是第 17 个被展开的顶点，层数是 8。这说明 BFS 认为“至少 8 步才能到”，和曼哈顿距离给出的下界完全一致。回溯 parent 得到路径：

$$(0,0)\to(1,0)\to(2,0)\to(3,0)\to(4,0)\to(4,1)\to(4,2)\to(4,3)\to(4,4)$$

这条路径绕到地图最下面，再从下边缘走到终点，一共 8 步。为什么绕路？因为第 2 列从上到下三格都是墙，直接向右走会被挡住，必须先向下绕开墙。这也说明启发式“只看坐标”的估计（8）正好等于真实最短步数——但这个例子太整齐了，真实地图里墙往往会让最短路径更长。

4.4 为什么第一次遇到终点就一定是“最短”

BFS 的关键性质是：顶点第一次被“发现”时，它离起点的层数就是真正最短的步数。可以用一个“数学归纳法”的直观版本说明。

第 0 层只有起点，距离 0，当然最短。假设第 $k$ 层之前的所有顶点，第一次被发现时层数都等于真实最短距离。那么第 $k+1$ 层的顶点是怎么被发现的？一定是由某个第 $k$ 层的顶点 v 在展开时发现的。如果这个顶点存在一条更短的、少于 $k+1$ 步的路径，那么它应该在更早的层就被发现（因为那条更短路径上的前一个顶点会在更早的层展开它）。这与“第 $k+1$ 层才第一次被发现”矛盾。所以第一次发现时的层数就是最短距离。由于终点第一次被弹出时所在层就是它的最短步数，BFS 在**每步代价相同（都为 1）**的图里保证找到最短路径。

4.5 复杂度与优缺点

每个顶点最多入队一次、出队一次；每条边最多被检查两次（从它的两个端点各看一次）。所以时间大约是“顶点数 + 边数”的一个常数倍：

$$T(n)=O(V+E)$$

空间上，队列最多同时装着某一层的全部顶点，所以 $O(V)$。对于格子地图，$E$ 大约是 $V$ 的常数倍（四方向最多 4 倍），因此也可以粗略说 $O(V)$。

优点：实现简单、完备，且在无权图（每步代价相同）里保证最短。缺点：完全“不挑方向”，哪怕终点就在起点右边一格，它也会把起点左边整片区域都看完；它也不理解“沼泽更贵”，无法处理带代价的地图。处理带权重的地图，需要一种能读懂代价的方法，后面会专门介绍。

5 DFS：一条道走到黑，不行再回头

5.1 核心思想

如果你在走一个迷宫，有一种很笨但可靠的办法：沿着一面墙一直走，遇到死路就原路退回，换一个岔路口再试。这就是深度优先搜索（Depth-First Search，简称 DFS）：选定一个方向一直往前，直到走不动了，再回溯（backtrack）到最近的分叉点。

DFS 管理开放表用的正是第 3 节讲的栈：后进先出。刚刚发现的顶点优先展开，所以它总是“越走越深”，而不是像 BFS 那样“一层层扫平”。

5.2 伪代码

DFS(图 G, 起点 S, 终点 G):
  栈 = [S]
  记录 visited = {S}
  记录 parent = {S: 无}
  当 栈 非空:
    u = 栈.pop()               # 从栈顶取出（后进先出）
    如果 u == G: 根据 parent 回溯，返回路径
    对 u 的每个邻居 v:
      如果 v 不在 visited:
        visited.add(v)
        parent[v] = u
        栈.append(v)           # 压到栈顶
  返回“无路可走”

和 BFS 的伪代码几乎一样，唯一的区别是把“队列”换成了“栈”。数据结构一换，行为完全不同——这就是算法设计的魅力。

5.3 在网格 A 上验算：它找到了一条更长的路

我在同一个网格 A 上跑了 DFS（邻居顺序：上、下、左、右，按这个顺序反向压栈），展开顺序如下：

$$(0,0)\,(1,0)\,(2,0)\,(3,0)\,(4,0)\,(4,1)\,(4,2)\,(3,2)\,(3,3)\,(2,3)\,(1,3)\,(0,3)\,(0,4)\,(1,4)\,(2,4)\,(3,4)\,(4,4)$$

它一路向下冲到第 4 行，再向右、向上探索，最后兜了一大圈才到终点。回溯出的路径是：

$$(0,0)\to(1,0)\to(2,0)\to(3,0)\to(4,0)\to(4,1)\to(4,2)\to(3,2)\to(3,3)\to(3,4)\to(4,4)$$

这条路径长 10 步，而 BFS 找到的是 8 步。同样展开 17 个顶点，DFS 找到的却不是最短路径。结论：DFS 不保证最短，它只保证“找到一条路”（如果存在）。

5.4 复杂度与优缺点

时间复杂度和 BFS 一样是 $O(V+E)$：每个顶点最多入栈一次、出栈一次。空间上有个优势：栈里最多只装“当前这条路线沿途的分叉点”，通常比 BFS 的整层队列小得多，最坏情况是 $O(V)$。

优点：内存省、实现简单、在“只要找到一条路就行”的场景（比如迷宫生成、判断连通性）非常好用。缺点：不保证最短，而且容易一头扎进“看起来很深的死胡同”，在超大图上可能先浪费大量时间走一条完全错误的方向。

6 Dijkstra：给每条路贴上“累计代价”

6.1 为什么 BFS 对付不了沼泽

现在地图上出现了“贵”的格子：普通路走一步代价 1，沼泽走一步代价 3。BFS 只看“走了几步”，会理直气壮地选一条 8 步的路，哪怕这条路要踩 3 格沼泽；而另一条绕远一点的 8 步路全是普通路，代价小得多。要处理权重，必须把注意力从“步数”转到“累计代价”。

迪杰斯特拉算法（Dijkstra’s algorithm） 的做法是：维护每个顶点当前已知的“从起点到它的最小累计代价” $d(u)$，每次从开放表里挑 $d(u)$ 最小的顶点展开，并尝试用“先到 u、再走一步到 v”来刷新邻居 v 的代价。开放表用的正是优先队列：谁累计代价小谁先被处理。

6.2 伪代码

Dijkstra(图 G, 起点 S, 终点 G):
  对每个顶点 u: d(u) = 无穷大
  d(S) = 0
  优先队列 = [(0, S)]
  记录 parent = {}
  当 优先队列 非空:
    (cost, u) = 优先队列.pop()     # 取出累计代价最小的
    如果 u 已经被“定案”: 跳过
    标记 u 为“定案”
    如果 u == G: 回溯返回路径
    对 u 的每条边 (u, v, w):
      新代价 = cost + w
      如果 新代价 < d(v):
        d(v) = 新代价
        parent[v] = u
        优先队列.push((新代价, v))
  返回“无路可走”

这里有个细节：同一个顶点可能被放进优先队列好几次（每次发现更小的代价），所以弹出时要检查它是不是已经“定案”，避免重复处理。

6.3 在带地形代价的网格 B 上验算

现在换一张图，叫网格 B。它没有墙，但有些格子是沼泽（代价 3），其余是普通路（代价 1）。起点 $(0,0)$，终点 $(4,4)$，四方向移动，走进某个格子的代价就是该格子的数字：

列     0   1   2   3   4
行 0   1   1   3   1   1
行 1   1   1   3   1   1
行 2   1   3   3   1   1
行 3   1   1   1   1   1
行 4   1   1   1   1   1

脚本运行后，出队（定案）顺序是：

$$(0,0)d0\;(0,1)d1\;(1,0)d1\;(1,1)d2\;(2,0)d2\;(3,0)d3\;(0,2)d4\;(3,1)d4\;(4,0)d4\;(0,3)d5\;(1,2)d5\;(2,1)d5\;(3,2)d5\;(4,1)d5\;(0,4)d6\;(1,3)d6\;(3,3)d6\;(4,2)d6\;(1,4)d7\;(2,3)d7\;(3,4)d7\;(4,3)d7\;(2,2)d8\;(2,4)d8\;(4,4)d8$$

每个格子的最终 $d$ 值如下表（∞ 表示还没定案时，最终全部定案）：

$$\begin{array}{c|ccccc} & 0 & 1 & 2 & 3 & 4\\ \hline 0 & 0 & 1 & 4 & 5 & 6\\ 1 & 1 & 2 & 5 & 6 & 7\\ 2 & 2 & 5 & 8 & 7 & 8\\ 3 & 3 & 4 & 5 & 6 & 7\\ 4 & 4 & 5 & 6 & 7 & 8 \end{array}$$

注意看 $d(0,2)=4$：从起点到 $(0,2)$ 必须踩沼泽，代价是 $1+3=4$（先到 $(0,1)$ 代价 1，再进沼泽加 3）。而 $d(4,4)=8$，对应路径：

$$(0,0)\to(1,0)\to(2,0)\to(3,0)\to(3,1)\to(3,2)\to(3,3)\to(3,4)\to(4,4)$$

这条路径全程踩普通路，代价 8。BFS 如果只看步数，会选经过 $(0,1)\to(0,2)$ 的那条 8 步路线，代价是 $1+3+1+1+1+1+1+1=10$。同样 8 步，代价差 2——这就是权重的意义。

6.4 为什么“弹出即定案”：一个贪心论证

Dijkstra 看起来像在“赌”：凭什么当前弹出的一定是最短？因为所有边的权重都非负。假设 u 被弹出时，其实还存在一条更便宜的、绕道去 u 的路。那条路从“已经定案的区域”走到“还没定案的区域”时，一定先经过某个还没定案的顶点 v，而且 v 的已知代价 $d(v)$ 一定不小于 $d(u)$（否则优先队列会先弹出 v）。从 v 到 u 的所有边权重都非负，所以整条绕道路的代价不小于 $d(v)$，更不小于 $d(u)$。矛盾。所以 u 被弹出时的 $d(u)$ 就是真正最短代价，可以直接“定案”。

这个论证同时说明了 Dijkstra 的适用范围：权重必须非负。如果出现负权重边，“先弹出”就不再安全，需要别的算法（本文不展开）。

6.5 复杂度与优缺点

使用二叉堆实现优先队列时，每个顶点最多定案一次（$V$ 次弹出），每条边最多引起一次“入队”（$E$ 次），每次入队或弹出大约 $\log V$ 次比较：

$$T(n)=O((V+E)\log V)$$

空间是 $O(V)$（每个顶点存一个距离、一个 parent）。

优点：能处理非负权重地图，并且保证代价最小；它是很多导航算法的地基。缺点：它同样“不挑方向”——即使终点就在右边，它也会把左边所有代价更小的区域先看完；在巨大的地图上，这仍然太慢。下一节开始，我们给搜索装上“方向感”。

7 Greedy Best-First：只盯着目标的急性子

7.1 核心思想

前面两个方法都“不看终点”：BFS 一层层平推，Dijkstra 按累计代价扩张。现在给搜索装上“方向感”：每次从开放表里挑 $h(n)$ 最小（也就是“看起来离终点最近”）的顶点展开。这就是贪心最佳优先搜索（Greedy Best-First Search），简称 Greedy。

它的思路非常像急性子导航：每次只问“哪个方向能让我看起来离终点最近？”完全不关心已经花了多少代价。$h(n)$ 正是第 2.3 节的距离估计，比如曼哈顿距离。

7.2 伪代码

Greedy(图 G, 起点 S, 终点 G, 启发式 h):
  优先队列 = [(h(S), S)]
  记录 visited = {S}
  记录 parent = {S: 无}
  当 优先队列 非空:
    (估, u) = 优先队列.pop()      # 挑 h 最小的
    如果 u == G: 回溯返回路径
    对 u 的每个邻居 v:
      如果 v 不在 visited:
        visited.add(v)
        parent[v] = u
        优先队列.push((h(v), v))
  返回“无路可走”

7.3 一个反例：它被“看起来很近”骗了

看下面这张只有 4 个顶点的小图，边上的数字是代价，括号里是启发式 $h$：

S --2--> A --100--> G        h(A)=1
S --10--> B --10--> G        h(B)=10

从 S 出发，Greedy 会先比较 A 和 B：$h(A)=1$ 比 $h(B)=10$ 小得多，于是先走 A。到了 A 之后只有一条路去 G，总代价 $2+100=102$。但真正的最优路线是走 B：$10+10=20$。Greedy 完全没看“已经花了多少”，被 A 的“看起来很近”骗进了深渊。

我在网格 A 上也跑了一遍 Greedy（曼哈顿距离、四方向），它只展开了 9 个顶点就到达终点，路径长 8 步，和最优一样。但这是运气：这面墙的形状恰好没骗到它。把墙的位置稍微改一改，它就可能先冲向墙再绕一大圈。结论：Greedy 通常非常快，但不保证最优，甚至可能找到很离谱的路线。

7.4 优缺点

优点：展开的顶点通常很少，速度快，特别适合“只要快速找到一条像样的路”的场景。缺点：不保证最优，容易被启发式误导；在极端情况下可能走很长很长的弯路才到终点。

8 A*：把“已花的”和“还要花的”加起来

8.1 从两个极端到平衡：f = g + h

Dijkstra 只看“已花的代价” $g(n)$，所以它不挑方向，慢但稳。Greedy 只看“估计还要花的代价” $h(n)$，所以它方向感强，快但容易翻车。一个自然的想法是：把两个数字加起来。

$$f(n)=g(n)+h(n)$$

其中 $g(n)$ 是从起点 $S$ 到 $n$ 的已知累计代价，$h(n)$ 是从 $n$ 到终点 $G$ 的估计剩余代价。$f(n)$ 是对“从 S 出发、经过 n、到达 G 的整条路总代价”的估计。每次从开放表里挑 $f(n)$ 最小的顶点展开——这就是 A* 算法。

为什么这样平衡有用？当 $h$ 比较准的时候，$f$ 会“偏爱”那些既没花太多、又确实朝终点走的方向；当 $h$ 不准（高估）时，$f$ 会“偏爱”那些先花得少但后面要花很多的路。所以 $h$ 的质量直接决定 A* 的表现。

8.2 两个关键性质：可采纳与一致

可采纳（admissible）：对任意顶点 $n$，启发式估计不超过真实最短剩余代价 $h^*(n)$：

$$h(n)\le h^*(n)$$

意思是“永远不把剩下的路想得比实际更短”。前面提过，三种网格距离都满足这个性质，因为“直线/街道距离”不可能比绕开墙之后的真实距离更长。

一致（consistent）：对任意一条边 $(n,a,n')$，满足三角不等式：

$$h(n)\le c(n,a,n')+h(n')$$

直觉是“从 n 到终点的估计，不应该比‘先走到邻居 n’，再从 n’ 到终点’还长”。一致比可采纳更强：一致一定可采纳（把最优路径上的边一条条加起来即可证明），而且一致还有一个额外好处——沿着任何一条路走，$f$ 值不会下降：

$$f(n')\ge f(n)$$

因此每个顶点只需处理一次，不需要“重新打开”。网格距离（曼哈顿、欧氏、八格）都满足三角不等式，所以都是一致的。

8.3 反例：不可采纳的启发式会让 A* 失去最优性

如果 $h$ 高估了某个顶点，A* 可能提前宣布“找到了”，却错过真正的最优路。看这个小图：

S --1--> C --3--> G          h(C)=6（真实剩余 3，被高估成 6）
S --2--> B --3--> G          h(B)=3（真实剩余 3，准确）
h(S)=4, h(G)=0

真实最优是 $S\to C\to G$，代价 $1+3=4$。A* 启动时开放表只有 S，$f(S)=4$。展开 S 后：

• C 的 $f=1+6=7$；
• B 的 $f=2+3=5$。

A* 先弹出 B（$f=5$），进而发现 G，$g(G)=2+3=5$。此时 C 还躺在开放表里（$f=7$），而 A* 的规则是“弹出 G 就结束”。于是它返回代价 5 的路径 $S\to B\to G$，比真正最优的 4 大。问题出在哪？$h(C)=6$ 把最优路线“伪装”得很贵，让 A* 误以为 B 那条路更好。我用脚本验算了这个例子，结果正是如此：返回 5，最优是 4。

这个反例说明：可采纳不是可选优化项，而是 A* 最优性的“入场券”。

8.4 证明：可采纳时，A* 找到的一定是最优

设 $C^*$ 是真正最短路径的总代价，并假设 A* 弹出终点 G 时返回的 $g(G)>C^*$。考虑那条真正最优的路径 $P^*$。在 G 被弹出的那一刻，$P^*$ 上一定存在“第一个还不在关闭表里的顶点” $n$。

• 如果 $n=G$，说明 G 是被沿最优路径发现的，那么 $g(G)=C^*$，与假设矛盾；
• 否则 $n$ 还在开放表里。由于 $n$ 在最优路径上，$g(n)$（沿最优前缀的代价）满足 $g(n)\le C^*-h^*(n)$；又因为 $h$ 可采纳，$h(n)\le h^*(n)$，所以：

$$f(n)=g(n)+h(n)\le C^*$$

而 A* 每次都弹出 $f$ 最小的顶点，它却先弹出了 $f(G)=g(G)>C^*$ 的 G——这与 $n$ 的 $f(n)\le C^*<f(G)$ 矛盾。所以假设不成立，$g(G)=C^*$。可采纳 ⇒ A 最优。*

8.5 在网格 A 上逐步验算

回到网格 A（曼哈顿距离，四方向）。脚本记录下了 A* 每次弹出的顶点、$g$、$h$、$f$：

弹出顺序	顶点	g	h	f
1	(0,0)	0	8	8
2	(0,1)	1	7	8
3	(1,0)	1	7	8
4	(1,1)	2	6	8
5	(2,0)	2	6	8
6	(2,1)	3	5	8
7	(3,0)	3	5	8
8	(3,1)	4	4	8
9	(4,0)	4	4	8
10	(3,2)	5	3	8
11	(4,1)	5	3	8
12	(3,3)	6	2	8
13	(4,2)	6	2	8
14	(3,4)	7	1	8
15	(4,3)	7	1	8
16	(4,4)	8	0	8

最后回溯出的路径是：

$$(0,0)\to(0,1)\to(1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)\to(3,4)\to(4,4)$$

代价 8，和 BFS 一样最短。A* 一共弹出 16 个顶点（比 BFS 的 17 个略少），开放表里最后还躺着 $(2,3)$ 和 $(2,4)$，它们的 $f=10$，因为“已经绕到墙后面再回来”看起来不划算，所以从没被弹出。在这个小地图上 A* 的优势不明显，因为曼哈顿距离恰好和真实走廊长度一样；在大地图上，$f$ 会把搜索牢牢“吸”向终点方向，节省的顶点数非常可观。

8.6 复杂度与优缺点

最坏情况下（比如 $h\equiv0$，退化成 Dijkstra），A* 的复杂度是 $O((V+E)\log V)$，空间 $O(V)$。但启发式越好，实际展开的顶点越少；如果 $h$ 恰好等于真实剩余代价，A* 会像“开卷考试”一样几乎只沿最优路径走。启发式越接近真实，A* 越快，但代价是计算 $h$ 本身可能更贵——这是另一个需要权衡的地方。

优点：可采纳时保证最优；一致时每个顶点只需处理一次；通常比 Dijkstra 快得多。缺点：开放表可能仍然很大；$h$ 高估会破坏最优性；在超大开放地图上内存仍是瓶颈。

9 双向搜索：两头一起挖隧道

9.1 双向 BFS：从两边同时扩散

想象挖一条穿山隧道：如果只从山的一侧挖，要挖完整条隧道；如果两头同时挖，每头只挖一半。双向 BFS 就是这个思路：从起点 $S$ 和终点 $G$ 同时做 BFS，一边一层地扩散，直到两边的“扩散圈”相遇，再把两段路接起来。

为什么能省？假设最短路径要走 $d$ 步，分支因子是 $b$。单方向 BFS 最坏要“看”大约 $b^d$ 个顶点（当然实际地图会有墙、会少很多）；双向 BFS 每边只要扩散到大约第 $d/2$ 层：

$$b^{d/2}+b^{d/2}=2b^{d/2}\ll b^d$$

举个例子：$b=4$、$d=10$ 时，$4^{10}=1048576$，而 $2\cdot4^5=2048$——差了五百多倍。层数越深，双向的优势越夸张。

9.2 在网格 A 上验算

我在网格 A 上跑了双向 BFS：正向从 $(0,0)$ 扩散，反向从 $(4,4)$ 扩散，两边各扩散了 4 层后在顶点 $(4,0)$ 相遇。正向访问了 9 个顶点，反向访问了 14 个顶点，合计 23 个；单方向 BFS 访问 17 个。咦，双向反而更多？

这是因为地图太小，两边的“扩散圈”互相重叠、重复劳动，而省下来的“深度”还不够补偿。双向搜索省的是“深度”，代价是“宽度”翻倍：在小地图上往往不划算，在“又宽又深”的大地图上才真正发威。这也提醒我们：算法评价要看规模，不能只看一个例子。两段路径接起来后得到：

$$(0,0)\to(1,0)\to(2,0)\to(3,0)\to(4,0)\to(4,1)\to(4,2)\to(4,3)\to(4,4)$$

代价 8，仍然最短。

9.3 双向 A*：两个方向都带“方向感”

把双向思想装进 A*，就是双向 A*。正向搜索用 $h_F(n)=$ 到 $G$ 的距离估计，反向搜索用 $h_B(n)=$ 到 $S$ 的距离估计；两边都按各自的 $f=g+h$ 挑顶点。当某个顶点同时出现在两边的关闭表里，就把“正向走到它”和“反向走到它”的两段路接起来。

我在网格 A 上跑了一个教学版双向 A*：正向关闭表 10 个顶点、反向关闭表 9 个顶点，在 $(3,2)$ 相遇，接出的路径代价 8。这里两边的合计（19）比单方向 A*（16）还多——和双向 BFS 一样，小地图上重叠太多。教学版的另一个问题是：“关闭表一相遇就停”并不保证最优，两边各自找到的可能是局部最优，接起来却绕路。

严格的最优停止条件需要多记一个量：设 $\mu$ 是“目前已经发现的最好完整路径”的代价（任意一个相遇点 $u$ 都给出候选 $g_F(u)+g_B(u)$，取其中最小者）。当两边的优先队列里最小的 $f$ 都满足：

$$\min f_F \ge \mu \quad\text{且}\quad \min f_B \ge \mu$$

就可以停止：因为任何还没走完的候选，其完整代价至少是它当前的 $f$，已经不可能打败 $\mu$ 了。这个条件保证了双向 A* 返回的 $\mu$ 就是最优代价。

9.4 优缺点

优点：理论上能把“指数深度”减半，在深而宽的地图上非常省；适合起点和终点都明确、且距离较远的场景。缺点：实现更复杂（要维护两套表、两套 parent），停止条件容易写错；地图小时反而更慢。教学演示里常见的“相遇即停”版本不保证最优，工程上必须用 $\mu$ 条件。

10 JPS：把一整条直线“跳”过去

10.1 问题：均匀网格上有大量“对称”路线

在八方向、每步代价相同的均匀网格里，从 A 到 B 有大量“长得不一样但代价一样”的路：先向右再向下，和先向下再向右，代价完全相同。A* 会把它们一个个都看一遍，纯属浪费。跳点搜索（Jump Point Search，简称 JPS） 的思路是：既然中间这些“顺路”的顶点都不影响结果，那就不要逐个展开，直接沿着直线“跳”到下一个关键顶点。

关键顶点叫跳点（jump point）：要么是终点，要么是“必须在这里停下来”的拐点。JPS 只把跳点放进开放表，中间扫过的顶点全部跳过。它和 A* 配合：外层还是 A* 的 $f=g+h$ 主循环，只是“展开一个顶点”变成“朝八个方向跳，找到跳点”。

10.2 两个核心概念：自然邻居与强制邻居

在某个顶点 $x$ 看它的邻居，可以分成两类。

自然邻居（natural neighbor）：沿着当前运动方向继续走会遇到的邻居。比如你正在向右走，那么右边的格子和右上的格子就是自然邻居——它们“顺路”。搜索只需要考虑自然邻居，其他方向都可以剪掉。

强制邻居（forced neighbor）：本来可以剪掉，但因为墙的存在，必须从这里拐弯才能不漏掉最短路径的邻居。形式化地说，对直线移动方向 $d$，顶点 $n$ 有强制邻居当且仅当存在一个侧向格子 $s$ 满足：

$$\mathrm{pass}(n+s)=\mathrm{true} \quad\text{且}\quad \mathrm{pass}(n+s-d)=\mathrm{false}$$

白话就是：$n$ 旁边明明有路（$n+s$ 可通行），但如果你是从 $d$ 方向滑过来的，要走进 $n+s$ 必须穿过格子 $n+s-d$，而那里是墙——所以走到 $n$ 时必须停下来，否则会漏掉这条路。出现强制邻居的 $n$ 就是一个跳点。

10.3 跳跃规则

1. 直线跳：沿一个直线方向一格一格看。如果看到终点，终点就是跳点；如果当前格有强制邻居，当前格就是跳点；否则继续往前，直到撞墙或出界。
2. 对角跳：沿对角线走时，除了检查自身有没有强制邻居，还要“顺便”检查两个正交方向（横和竖）——如果其中某个正交方向能跳出一个跳点，那么当前格也是跳点。

伪代码（简化版）：

jump(x, dx, dy):
  n = x 沿 (dx,dy) 走一格
  如果 n 不可通行: 返回 无
  如果 n 是终点: 返回 n
  如果 n 有强制邻居: 返回 n
  如果 (dx,dy) 是对角线:
    如果 jump(n, dx, 0) 或 jump(n, 0, dy) 有结果: 返回 n
  返回 jump(n, dx, dy)      # 继续跳

10.4 在网格 A 上验算：只展开 6 个跳点

还是网格 A，这次用八方向移动、切比雪夫式八格距离做启发式。脚本记录下的“跳跃”过程和展开的跳点如下（g 是累计代价，f=g+h）：

$$(0,0)\xrightarrow{\text{对角}}(1,1)\xrightarrow{\text{下}}(3,1)\xrightarrow{\text{右}}(3,3),\quad(3,1)\xrightarrow{\text{对角}}(4,2)\xrightarrow{\text{右}}(4,4)$$

展开的跳点共 6 个：

跳点	g	f	为什么是跳点
(0,0)	0	5.66	起点
(1,1)	1.41	5.66	对角跳时，下方直线可跳到 (3,1)
(3,1)	3.41	6.83	有强制邻居 (3,2)：从上方下来时，(2,2) 是墙但 (3,2) 可通行
(4,2)	4.83	6.83	向右直线扫描直接看到终点
(3,3)	5.41	6.83	有强制邻居 (3,2)（对称原因）
(4,4)	6.83	6.83	终点

最终路径：

$$(0,0)\to(1,1)\to(3,1)\to(4,2)\to(4,4)$$

代价 $2\sqrt2+2+2\sqrt2=4+2\sqrt2\approx6.828$。八方向移动允许斜穿，所以比四方向的 8 步更短。关键是：A 在这个网格上展开了 16 个顶点，JPS 只展开了 6 个跳点*，中间那些“顺路”的格子全被跳过了。

10.5 复杂度、适用条件与优缺点

最坏情况下 JPS 和 A* 同阶（$O(E\log V)$），但实际展开的顶点通常少一个数量级以上，而且不需要任何预处理，地图临时改几块墙也能立即重新搜索。

但 JPS 有一个严格前提：地图必须是均匀代价网格（每步代价相同、八方向、规则障碍）。一旦引入地形代价（沼泽 3、山路 5），或者允许任意角度移动，“中间格子全跳过”就不再安全——因为代价不均匀时，中间格子的选择会影响总代价。可视化实验室遇到地形代价时会自动切回 A*。

优点：均匀网格上极快、内存省、实现不依赖额外预处理。缺点：只适用于均匀网格；在最坏情况下（迷宫式窄道）跳点可能退化成几乎所有格子，优势消失。

11 对比总结：谁最快、谁最优、什么时候用谁

把所有方法放在同一张表里看，优劣和分工一目了然。表中的时间复杂度是典型实现（二叉堆优先队列）的结果，$V$ 是顶点数，$E$ 是边数：

方法	待办清单	是否保证最短	典型时间	典型空间	最擅长
BFS	队列	无权图：是；有权图：否	$O(V+E)$	$O(V)$	无权图最短步数
DFS	栈	否	$O(V+E)$	$O(V)$ 但通常很小	只求找到一条路、迷宫、连通性
Dijkstra	优先队列（按 g）	权重非负：是	$O((V+E)\log V)$	$O(V)$	有权图最短代价
Greedy	优先队列（按 h）	否	通常远小于 A*	$O(V)$	只求快、不求最优
A*	优先队列（按 f=g+h）	h 可采纳：是	最坏 $O((V+E)\log V)$	$O(V)$	有权图上的“又快又最优”
双向 BFS	两个队列	无权图：是	理想 $O(b^{d/2})$	两个 $O(b^{d/2})$	深而宽的无权图
双向 A*	两个优先队列	用 μ 条件停止：是	理想 $O(b^{d/2})$	两个开放表	距离很远的有权图
JPS	优先队列 + 跳点	均匀网格：是	同 A*，实际少很多	$O(V)$	均匀代价网格游戏地图

选择方法的决策树可以这样走：

决策树的第一问“要不要最优”比任何算法细节都更能决定选型：只要一条像样的路就选 DFS 或 Greedy，要求保证最短才轮到 BFS、Dijkstra、A* 与 JPS。

一句话总结各方法的定位：BFS 是地基，Dijkstra 给地基加了权重，Greedy 给地基装了方向感，A 把两者缝在一起，双向搜索把深度劈成两半，JPS 再把均匀网格里的直线一口气跳过。*

12 动手实验：在可视化实验室里亲眼观察

纸上得来终觉浅。我在 Playground 放了一个寻路算法可视化实验室，支持本文讲的全部八种方法。建议按下面的步骤玩：

1. 先把算法选成 BFS，画几块墙，点“开始寻路”，观察它像洪水一样一层层扩散，最后高亮出最短路径；
2. 切到 DFS，同样的地图再看一遍：路径变长了吗？展开顺序是不是“一条道走到黑”？
3. 用“地形”画笔把几个格子刷成代价 2 或 3，再跑 Dijkstra 和 A*，对比两条路径：谁会绕着沼泽走？
4. 把启发式从“切比雪夫”换成“曼哈顿”，在八方向移动下观察 A* 的路径——曼哈顿在八方向下会高估代价，结果可能非最优，这就是本文第 8.3 节反例的放大版；
5. 最后试试双向 BFS、双向 A* 和 JPS，看两边如何“会师”、JPS 如何一路“跳”过去；
6. 点击“递归分割”一键生成迷宫，再用不同算法挑战它，比较界面上的“访问节点”和“耗时”统计。

iframe 嵌在下面，直接就能玩：

13 结论

寻路问题表面简单，背后是一整套“用空间换时间、用知识换搜索”的设计哲学。本文从地图建模出发，沿着一条清晰的脉络走完了八种方法：先学会展开与回溯，再学会按层扩散，再学会读懂代价，再学会看目标，最后学会把目标与代价结合、把搜索劈成两半、把整段直线跳过。

如果只记三件事，请记住这三条：第一，BFS 管无权、Dijkstra 管有权，这是正确性的底线；第二，A 的灵魂是“可采纳”的启发式*，$f=g+h$ 的平衡让它在最优与高效之间站稳；第三，没有任何方法在所有场景都最好——地图的形状、代价的分布、是否要求最优，决定了你应该拿起哪把工具。

14 常见疑问：把容易踩的坑一次说清

为什么 Dijkstra 要求权重非负？ 因为“弹出即定案”的证明依赖“绕道只会更贵”。一旦出现负权边，先弹出的顶点可能被后来发现的一条“负权绕道”刷新成更小代价，前面的定案就作废了。处理负权图需要 Bellman-Ford 这类能反复松弛的方法，代价是更慢。

A 的启发式 h 是不是越大越好？* 分两层看：在“可采纳”的约束内，h 越接近真实剩余代价，A* 展开的顶点越少，越快；一旦 h 超过真实值，就丧失了最优性（第 8.3 节的反例）。所以工程上常见的做法是选一个“尽量大但不超过真实值”的启发式，比如八方向网格用八格距离而不是曼哈顿距离。

JPS 是不是比 A 更强？* 不是。JPS 可以理解成“A* 的加速插件”：外层循环、启发式、开放表全都一样，只是把“逐格展开”换成了“直线跳跃”。在均匀代价网格上它大幅减少展开数，但换成带地形成本的网格就失效。所谓“最强算法”并不存在，只有“最适合当前地图”的算法。

双向搜索为什么有时候反而更慢？ 因为它把“一份深度 d 的搜索”变成“两份深度 d/2 的搜索”，两份搜索的扩散圈在中间区域大量重叠；地图越小、越窄，重叠越严重。双向搜索的真正主场是“又宽又深”的地图，比如 $b^d$ 天文数字的场景。

地图会动态变化怎么办？ 本文的方法都假设地图静止。如果墙壁、代价频繁变化，工程上常用 D* Lite、LPA* 这类“增量式”方法：它们复用上一次的搜索结果，只重算受影响的部分。那已经超出本文的入门范围，但理解 A* 是理解它们最好的起点。

为什么教程里 A 只比 BFS 少展开一个顶点？* 因为网格 A 的走廊形状让曼哈顿距离恰好等于真实剩余步数，A* 沿走廊前进时 $f$ 恒定，几乎和 BFS 一样“平推”。如果 h 更松（比如地图上有很多凹形障碍），A* 的优势才会明显放大。这个例子也说明：评价算法要用多种地图，不能只看一个“运气好”的例子。

如果只想快速实现一个“能用”的寻路，选什么？ 二维游戏网格：首选 A*（可采纳启发式）；要求极速且地图是均匀网格：用 JPS；有地形代价：A* 或 Dijkstra；只要一条路：DFS。记住这条路线，你已经在大多数实战场景里不会选错。

参考资料

1. Breadth-first search Wikipedia
2. Depth-first search Wikipedia
3. Dijkstra's algorithm Wikipedia
4. A* search algorithm Wikipedia
5. Introduction to the A* Algorithm Red Blob Games
6. Implementation of A* Red Blob Games
7. CS188: Search project UC Berkeley
8. Online Graph Pruning for Pathfinding on Grid Maps Harabor & Grastien 路 AAAI 2011
9. Introduction to Algorithms (CLRS) MIT Press 路 Cormen, Leiserson, Rivest, Stein