A* Search Algorithm
A*（A-star）是图与网格上最常用的最短路径搜索算法，它把 Dijkstra 的“稳”和贪心最佳优先搜索的“快”合二为一。本文从最短路径问题与这两个前辈算法讲起，一步步把 $f(n)=g(n)+h(n)$、最优性条件、启发式设计与常见变体讲清楚，只需要基础的图与优先队列知识即可跟下来。
问题与起点：最短路径、Dijkstra 与贪心最佳优先
在动手讲 A* 之前，我们得先把舞台搭好。A* 不是凭空冒出来的算法，它是为了解决一个非常具体的问题，并且站在两个前辈算法的肩膀上：一个保证找到最优解但“很笨”，一个跑得很快但“会走偏”。理解了这两个前辈的长处与短处，你才会明白 A* 为什么是“取两者之长”，也才会真正体会到它的精妙。这一节我们就一步一步把这个起点讲清楚。
一、把问题讲清楚：图与网格上的最短路径
我们要解决的核心问题是最短路径问题（shortest path problem）：从一个起点出发，到达一个终点，找一条总代价（cost）最小的路。
听起来很朴素，但要让计算机能处理，我们必须把它抽象成数学对象，也就是图（graph）。一个图由两样东西构成：
- 节点（node），也叫顶点（vertex）：表示一个个“状态（state）”或“位置（position）”。比如地图上的一个路口、网格里的一个格子、游戏里角色所在的一个位置。
- 边（edge）：表示节点之间的“连接”或“可以从一个状态走到另一个状态”的关系。每条边上带着一个权重（weight），也就是走这条边所要付出的代价（cost）。
我们用一些记号把它写规范一点。设节点 $u$ 和节点 $v$ 之间有一条边，这条边的代价记作 $c(u, v)$，它通常是一个非负数（这一点后面很重要）。从起点 $s$（start）走到终点 $t$（target / goal），一条路径就是一串首尾相接的节点 $s = v_0, v_1, v_2, \ldots, v_k = t$，这条路径的总代价是把沿途每条边的代价加起来：
\[\text{total cost} = c(v_0, v_1) + c(v_1, v_2) + \cdots + c(v_{k-1}, v_k)\]我们的目标，就是在所有从 $s$ 到 $t$ 的路径里，找出总代价最小的那一条。这个最小总代价，我们常记作 $d(s, t)$，读作“从 $s$ 到 $t$ 的最短距离（shortest distance）”。
为了让你有更具体的画面感，我们用一个最常见的例子：网格地图（grid map）。想象一张方格纸，每个格子是一个节点。如果一个格子可以走到它上下左右相邻的格子，那么相邻格子之间就有一条边。如果每走一步代价都是 $1$，那么“最短路径”就是“步数最少的路”。有些格子是墙（障碍物），它们之间没有边，走不过去。游戏里角色寻路、扫地机器人规划路线，本质上都是这个网格最短路径问题。
这里有几个概念值得专门点出来，因为它们贯穿全文：
- 状态（state）：就是节点本身，它回答“我现在在哪”。在更复杂的问题里，状态可能不只是位置，还包括“手上拿着钥匙没有”“油还剩多少”，但在入门阶段，把状态理解成“位置”就够了。
- 边与代价（edge and cost）：边回答“我能往哪走”，代价回答“这一步要花多少”。代价可以是距离、时间、油耗、过路费等等。
- 起点与终点（start and goal）：问题的两端。
到这里，问题就定义清楚了：给定一个图（或网格），给定起点和终点，求一条总代价最小的路径。下面我们看两个经典算法是怎么解决它的。
二、Dijkstra 算法：稳扎稳打，一圈圈往外扩
第一个登场的是大名鼎鼎的 Dijkstra 算法（以荷兰计算机科学家 Edsger W. Dijkstra 命名）。它的核心思想可以用一句话概括：永远优先处理“目前已知离起点最近”的那个节点。
我打一个非常直观的比方。想象你把起点 $s$ 当成一滴墨水滴在纸上，墨水开始均匀地向四周扩散（渗开）。墨水会先浸到离起点近的格子，后浸到远的格子。Dijkstra 做的事情，就是模拟这种“按距离一圈一圈往外扩散”的过程：它总是先确定离起点最近的节点的最短距离，再确定次近的，再次近的，如此一层层往外推，直到扩散到终点为止。
我们把它说得稍微严谨一点。算法给每个节点 $v$ 维护一个值 $g(v)$，表示“目前为止找到的、从起点到 $v$ 的最短路径代价”。一开始，起点 $g(s) = 0$，其余所有节点的 $g$ 都设成无穷大 $\infty$（表示还没找到任何路）。然后算法反复做下面这件事：
1
2
3
4
5
6
7
8
1. 把起点放入优先队列，g(s) = 0，其余节点 g = ∞
2. 重复以下步骤，直到队列为空（或取出终点）：
a. 从队列中取出 g 值最小的节点 u（这是关键：永远先处理最近的）
b. 标记 u 为"已确定"（它的最短距离 g(u) 此刻已是最终值）
c. 对 u 的每个邻居 v：
if g(u) + c(u, v) < g(v): # 经过 u 走到 v 更划算
g(v) = g(u) + c(u, v) # 更新 v 的最短距离（这一步叫"松弛"）
记录 v 的前驱为 u # 方便最后回溯出路径
这里步骤 c 中的更新操作，专业术语叫做松弛（relaxation）：每发现一条更短的路，就把对应节点的 $g$ 值“放松”得更小一点。步骤 a 中“取出 $g$ 值最小的节点”，是靠一个优先队列（priority queue）（通常用最小堆实现）来高效完成的。
为什么 Dijkstra 一定能找到最优解？ 直觉上是这样：因为所有边的代价都非负，所以当一个节点被“取出并确定”时，没有任何还没确定的节点能提供一条更短的路绕过来。墨水扩散的比喻里也是同样的道理：墨水不会“跳过近处直接浸到远处”，所以第一次浸到某个格子时，走过的距离一定是最短的。这就是 Dijkstra 的最优性（optimality）保证。（顺带一提，这个保证依赖“边代价非负”这个前提；如果存在负代价的边，Dijkstra 就可能出错，那是另一类算法要解决的问题了。）
那 Dijkstra 的毛病在哪？ 一个字：盲（blind）。它在扩散的时候，是完全不看终点在哪个方向的。墨水朝四面八方均匀渗开，可终点也许就在右边一点点，而墨水却傻乎乎地往左边、往上、往下也扩散了一大片。结果就是：它会扩展（expand）大量与终点毫不相关的节点，做了很多无用功。在一张很大的地图上，如果起点和终点离得很近但地图很大，Dijkstra 仍可能把起点周围一大圈节点都“渗”一遍才碰到终点。
用一句话总结 Dijkstra：
- 优点：保证找到最优解（最短路径），逻辑简单可靠。
- 缺点：盲目地朝各个方向扩散，不利用“终点在哪”的信息，扩展了很多无关节点，效率不高。
这就给我们留下一个很自然的疑问：既然我们知道终点在哪，能不能让搜索“朝着终点的方向走”，少做点无用功？这就引出了第二个算法。
三、贪心最佳优先搜索：一头扎向终点，但容易跑偏
第二个算法叫贪心最佳优先搜索（greedy best-first search）。它和 Dijkstra 几乎是两个极端。Dijkstra 只看“我已经走了多远”，而贪心最佳优先只看“我估计离终点还有多远”。
这里要引入一个全新的、极其重要的概念：启发式（heuristic），记作 $h(v)$。$h(v)$ 是一个估计值，它估计“从节点 $v$ 到终点 $t$ 还要花多少代价”。注意，它只是个估计，不是真实距离，因为真实距离往往要等你真的搜过去才知道，但我们想在搜索之前就有个“方向感”。
在网格地图上，一个最常用的启发式是曼哈顿距离（Manhattan distance）或欧几里得距离（Euclidean distance）。比如欧几里得距离就是直线距离：
\[h(v) = \sqrt{(x_v - x_t)^2 + (y_v - y_t)^2}\]它假装中间没有任何障碍物，直接量一下“直线上还差多远”。这个估计很便宜（一行公式就算出来了），又能粗略告诉我们“哪个节点看起来离终点更近”。
贪心最佳优先搜索的策略就是：每次都优先扩展启发式值 $h$ 最小的那个节点，也就是“看起来离终点最近”的节点。它的伪代码和 Dijkstra 几乎一样，唯一的区别是优先队列里排序用的不是 $g$，而是 $h$：
1
2
3
4
5
6
7
1. 把起点放入优先队列，按 h 值排序
2. 重复以下步骤，直到取出终点：
a. 从队列中取出 h(u) 最小的节点 u（永远先去"看起来最接近终点"的那个）
b. 对 u 的每个邻居 v：
如果 v 没访问过：
估计 h(v) = v 到终点的估计代价
把 v 放入队列，记录前驱为 u
注意这里和 Dijkstra 的关键差别：贪心最佳优先根本不累计“已经走了多远”这个代价 $g$，它只盯着“还差多远”的估计 $h$。
它的优点很明显：快。 因为它一门心思朝着终点的方向冲，在一张开阔、没什么障碍的地图上，它几乎是直线奔向终点，扩展的节点数远远少于 Dijkstra，效率高得多。墨水的比喻在这里不再适用，它更像一支“认准方向的箭”。
但它有一个致命的毛病：它不保证最优，而且容易被“带偏”。 问题就出在它“只看未来估计、不看已付出代价”。想象这样一个场景：终点在你的正前方，但正前方有一堵很长的墙挡着，真正的近路其实要先绕一小段远路（暂时离终点更远）才能通过一个缺口。贪心最佳优先因为只盯着 $h$，会固执地朝着“看起来更近”的方向钻，一头扎进死胡同，然后才被迫回头，结果走出一条又长又绕的烂路。它找到的路径可能比真正的最短路径长很多，甚至在某些情况下绕得离谱。
换句话说，它“目光短浅”：只看眼前哪一步看起来离目标近，而不管这一步会不会让自己付出更大的总代价。这正是“贪心（greedy）”这个名字的由来。
用一句话总结贪心最佳优先：
- 优点：利用启发式信息直奔终点，扩展节点少，速度快。
- 缺点：只看对未来的估计、忽略已经付出的代价，不保证最优，可能被障碍带偏、走出很绕的路。
四、对照与伏笔：A* 要把两者的长处合起来
现在我们把两个前辈摆在一起对比，矛盾就一目了然了：
| 算法 | 排序依据 | 关注点 | 优点 | 缺点 |
|---|---|---|---|---|
| Dijkstra | $g(v)$（已走代价） | 只看过去 | 保证最优 | 盲目扩散，扩展大量无关节点，慢 |
| 贪心最佳优先 | $h(v)$（估计剩余） | 只看未来 | 直奔终点，扩展少，快 | 不保证最优，容易被带偏走绕路 |
你应该已经隐约感觉到了：
- Dijkstra 只用 $g$（“我已经走了多远”），它保证最优但盲目。
- 贪心最佳优先只用 $h$（“我估计还差多远”），它快但会走偏。
一个只看过去，一个只看未来；一个稳但慢，一个快但不靠谱。两者各执一端，各有致命短板。那么一个再自然不过的问题就浮上来了：
能不能把这两个量结合起来，既考虑“已经走了多远”（保证不绕远路），又考虑“估计还差多远”（保证朝终点的方向走），从而做到既快又最优？
这正是 A* 算法的出发点。它的核心思想极其简洁优雅，就是把两个量加在一起，用 $f(v) = g(v) + h(v)$ 作为排序依据，让搜索同时拥有 Dijkstra 的“严谨”和贪心最佳优先的“方向感”。至于这个简单的相加为什么就能“取两者之长”、在什么条件下还能保证最优，正是接下来几节要细细展开的内容。带着上面这两个前辈的长短记在心里，你会发现 A* 的设计几乎是“水到渠成”。
A\* 的核心思想：f(n)=g(n)+h(n)
A* 算法（A-star）的全部精髓，几乎都浓缩在一个简单的等式里：
\[f(n) = g(n) + h(n)\]这一节我们就把这条公式彻底讲透。它看起来只是三个字母相加，但每一项的含义、它们为什么要相加、相加之后 A* 凭什么“聪明”，都值得一步一步说清楚。我们的目标是：让一个只有基础（知道什么是图、什么是节点、什么是优先队列）的读者，读完之后能用一句大白话复述出 A* 的灵魂。
先建立一个生活直觉：花钱的总预算
在正式拆解符号之前，先记住一个比喻，后面所有的推导都可以回到这个比喻上来。
想象你正在从家里出发去一个目的地，途中会经过很多个中转点（路口、车站、城市）。在某个中转点 $n$ 处，你想评估“如果走这条经过 $n$ 的路线，全程一共要花多少钱”。这个总花费可以拆成两部分：
- 已经花掉的钱：从起点一路走到 $n$，你已经实实在在掏出去的钱。这是确定的、已经发生的、不会再变的事实。
- 预估还要花的钱：从 $n$ 到目的地，你还没走，但可以拍脑袋估一个数（比如看地图直线距离折算成路费）。这是猜测，不一定准。
把这两部分加起来，就是“经过 $n$ 这条路线的总预算估计”：
\[\text{总预算} = \text{已花的钱} + \text{预估还要花的钱}\]A* 在每一步做的事，就是看手头所有“待考虑的中转点”，挑出那个“总预算最小”的去优先探索。这就是 A* 的全部直觉。下面我们把这个比喻里的每个词，换成算法里的符号。
g(n)：从起点到 n 的真实代价（已经花的钱）
$g(n)$ 表示“从起点（start）出发，沿着当前已经找到的那条路径，走到节点 $n$，一路上累积的真实代价”。
这里有几个关键词要扣住：
- 真实：$g(n)$ 不是估计，而是实打实地把路径上每一段边的代价加起来得到的。如果地图上每走一格花 $1$，那么走了 $5$ 格，$g$ 就是 $5$。如果不同的边有不同的权重（比如平地花 $1$、上坡花 $3$），就把这些权重老老实实加起来。
- 从起点出发：$g$ 衡量的是“过去”，是从 source 到 $n$ 这一段已经走完的旅程，对应比喻里“已经花掉的钱”。
- 沿着当前找到的路径：注意这里有个微妙之处。同一个节点 $n$，可能有多条路能到达，代价各不相同。A* 在搜索过程中，记录的是“目前发现的、到 $n$ 的最便宜路线”对应的 $g(n)$。如果后来又发现了一条更便宜的路通向 $n$，就要把 $g(n)$ 更新成更小的值（这一步叫“松弛”，relaxation）。
在最常见的网格寻路里，$g$ 的计算非常简单，是递推出来的。设 $p(n)$ 是在当前路径上 $n$ 的父节点（parent），$c(p(n), n)$ 是从父节点走到 $n$ 这一步的代价，那么：
\[g(n) = g(p(n)) + c(p(n), n)\]起点自己的代价是 $g(\text{start}) = 0$（从起点到起点，一分钱没花）。在每格代价都为 $1$ 的网格里，这条递推就退化成最朴素的形式：$g(n) = g(p(n)) + 1$，也就是“父节点的步数加一”。
一句话总结：$g(n)$ 是确定的、可累加的、关于过去的真实账单。
h(n)：从 n 到目标的启发式估计（预估还要花的钱）
$h(n)$ 表示“从节点 $n$ 出发，到达目标节点（goal）还需要多少代价”的一个估计值。这个 $h$ 就是 A* 里最有灵魂的东西，它的全名叫启发函数（heuristic function），A* 里的 “*” 某种意义上就在指它。
要点同样逐条扣：
- 估计，不是真值：和 $g$ 截然不同，$h(n)$ 是我们在“还没真正走过那段路”的情况下，凭某种规则猜出来的。它对应比喻里“预估还要花的钱”。
- 关于未来：$g$ 看过去，$h$ 看未来。$h$ 衡量的是从 $n$ 到目标那段“尚未发生”的旅程。
- 怎么估？用一个廉价又合理的规则。最常见的做法是用某种“几何直线距离”，因为算起来快，又大致反映远近：
- 在允许上下左右移动的网格里，常用曼哈顿距离（Manhattan distance）：$h(n) = \lvert x_n - x_{goal} \rvert + \lvert y_n - y_{goal} \rvert$。
- 在允许任意方向移动的场景里，常用欧几里得距离（Euclidean distance）：$h(n) = \sqrt{(x_n - x_{goal})^2 + (y_n - y_{goal})^2}$。
- 估计时通常“无视障碍”：启发函数一般只看 $n$ 和目标之间的直线远近，并不去考虑中间有没有墙、有没有绕路。正因为它无视障碍，它算出来的值往往会比“真正还要走的距离”偏小或相等，而绝不会高估。这个“不高估”的性质极其重要（它叫可接受性，admissibility），它正是保证 A* 能找到最优路径的关键。本节先点到为止，后续章节会专门展开。
一句话总结：$h(n)$ 是不确定的、靠规则猜出来的、关于未来的预估账单，它体现了我们对“目标在哪个方向、还有多远”的先验知识。
f(n)：经过 n 的整条路径总代价估计（总预算）
把过去的真实账单 $g(n)$ 和未来的预估账单 $h(n)$ 加起来，就得到了 A* 真正用来排序的那个量：
\[f(n) = g(n) + h(n)\]$f(n)$ 的含义是：如果最终的最优路径恰好经过节点 $n$，那么这条完整路径（从起点经过 $n$ 再到目标）的总代价，大约是 $f(n)$。
为什么说“大约”？因为前半截 $g(n)$ 是精确的，后半截 $h(n)$ 是估计的，所以两者之和 $f(n)$ 是一个“半精确、半估计”的总代价预测。它不是真值，但是一个有依据的猜测。
回到比喻：$f(n) = $ 已经花的钱 $+$ 预估还要花的钱 $=$ 这条路线的总预算。A* 关心的从来不是“我现在已经花了多少”（那只是 $g$），也不是“我看起来离目标还有多远”（那只是 $h$），而是这两者之和代表的“全程总账”。这是 A* 比只看其中一项的算法都更聪明的根本原因：它同时尊重已经付出的代价，又前瞻性地考虑了还要付出的代价。
A* 主循环：每次扩展 f 最小的节点
理解了三个量，A* 的运行机制就水到渠成了。A* 维护一个优先队列（priority queue），习惯上叫做 open list（开放列表），里面装着“已经发现、但还没有展开探索”的节点。队列以每个节点的 $f$ 值作为优先级，$f$ 越小，优先级越高。
算法的核心循环只有一句话：每次从优先队列里取出 $f$ 值最小的那个节点，把它展开（扩展它的所有邻居），然后继续。 直到取出的节点就是目标，搜索结束。
下面是 A* 的伪代码（pseudocode）骨架，重点在于体现 $f = g + h$ 是如何驱动整个过程的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def a_star(start, goal, neighbors, cost, h):
# g[n]: 从起点到 n 的当前最优真实代价
g = {start: 0}
# f[n] = g[n] + h(n)，优先队列按 f 排序
open_list = PriorityQueue()
open_list.put(start, priority=h(start)) # 起点 g=0, 所以 f=h
came_from = {start: None} # 记录路径，用于回溯
while not open_list.empty():
current = open_list.pop_min() # 取出 f 最小的节点
if current == goal:
return reconstruct_path(came_from, goal)
for nxt in neighbors(current):
# 走到 nxt 的新真实代价（已经花的钱）
new_g = g[current] + cost(current, nxt)
# 如果第一次到 nxt，或者发现了更便宜的路，就更新
if nxt not in g or new_g < g[nxt]:
g[nxt] = new_g
f = new_g + h(nxt) # f = g + h，灵魂所在
open_list.put(nxt, priority=f)
came_from[nxt] = current
return None # 队列空了还没到目标，说明无路可达
请把注意力放在 f = new_g + h(nxt) 这一行。整个算法的“智能”全部凝结在这里：
new_g是这一项里“已经花的钱”，由父节点的 $g$ 加上这一步的边代价递推而来。h(nxt)是“预估还要花的钱”，由启发函数即时算出。- 两者之和
f决定了nxt在优先队列里的位置，从而决定了它被探索的早晚。
A* 之所以高效，是因为它总是优先探索那些“看起来总预算最小”的节点。一个节点如果已经走了很远（$g$ 大），或者明显朝着远离目标的方向走（$h$ 大），它的 $f$ 就大，就会被排到队列后面，从而被推迟甚至永远不被探索。这就避免了在错误方向上浪费力气。
两个极端：A* 如何统一了 Dijkstra 与贪心
理解 $f = g + h$ 最深刻的方式，是看它的两个极端情况。A* 不是凭空发明的新算法，而是一个把两类经典思路统一在一根连续光谱上的框架。调节 $g$ 和 $h$ 的相对权重，A* 就会“变身”成你早已熟悉的算法。
极端一：令 $h \equiv 0$，A* 退化为 Dijkstra 算法。
如果启发函数恒等于零，也就是说我们对“未来还要走多远”完全没有任何信息（预估还要花的钱永远填 $0$），那么：
\[f(n) = g(n) + 0 = g(n)\]此时 A* 排序时只看 $g$，也就是只看“从起点到 $n$ 已经实际走了多远”。每次扩展“离起点已知最近”的节点，这恰好就是 Dijkstra 算法的行为。Dijkstra 是一种“盲目但稳妥”的算法：它不知道目标在哪个方向，于是像水波一样从起点向四面八方均匀扩散，谁离起点近就先探索谁。它一定能找到最优路径，但因为没有方向感，往往探索了大量无关节点，效率不高。
换句话说：Dijkstra 是 A* 在“对未来一无所知”时的特例。 $h$ 提供的方向信息一旦归零，A* 就丢掉了前瞻能力，只能退回到稳妥的全方位搜索。
极端二：只用 $h$（忽略 $g$），A* 退化为贪心最佳优先搜索。
反过来，如果我们在排序时只看 $h$，完全无视已经花掉的代价：
\[f(n) = h(n)\]此时 A* 每次都扑向“看起来离目标最近”的节点，不管为了到达这个节点已经付出了多大代价。这就是贪心最佳优先搜索（Greedy Best-First Search）。它的特点是“目标感极强、横冲直撞”：因为只盯着 $h$，它通常能很快冲到目标附近，速度往往比 Dijkstra 快得多。
但它有个致命弱点：因为完全不考虑已经走过的真实代价 $g$，它找到的路径不保证是最优的（最短的）。 它可能为了贪图“看起来更靠近目标”，而一头扎进一条绕了大远路或被障碍逼回的路线，最终走了冤枉路还浑然不觉。它“只看未来的诱惑，不算过去的成本”，所以容易被启发函数误导。
A* 站在两个极端的中间，取两者之长。
现在把两个极端放在一起对照，A* 的设计哲学就一目了然了：
| 算法 | 排序依据 | 直觉 | 是否最优 | 效率特点 |
|---|---|---|---|---|
| Dijkstra | $f = g$（只看过去） | 只算已花的钱，无方向感 | 保证最优 | 盲目扩散，慢 |
| 贪心最佳优先 | $f = h$（只看未来） | 只贪图靠近目标 | 不保证最优 | 有方向感，快但易跑偏 |
| A* | $f = g + h$（过去 + 未来） | 已花的钱 + 预估还要花的钱 | 在 $h$ 不高估时保证最优 | 有方向感，又稳妥 |
这张表里藏着 A* 的灵魂：
- $g$ 这一项让它“诚实”：始终记账，记得自己已经付出的真实代价，不会被表面上的“接近目标”所欺骗，从而保住了找到最优路径的能力（前提是 $h$ 不高估）。
- $h$ 这一项让它“有远见”：带着对目标方向的估计前进，不像 Dijkstra 那样四处乱撞，从而大幅减少无谓的探索，跑得快。
正是 $g$ 与 $h$ 的相加，让 A* 同时拥有了 Dijkstra 的“稳”（最优性）和贪心搜索的“快”（方向性）。$h$ 估得越准（越接近真实的剩余代价，但又不高估），A* 就越接近“只走在最优路径上”的理想状态，探索的节点就越少，效率就越高；$h$ 估得越保守（趋近于 $0$），A* 就越退回 Dijkstra 那种稳妥但缓慢的样子。这条由 $h$ 的“信息量”参数化出来的连续光谱，一端是 Dijkstra，另一端是贪心，而 A* 优雅地坐在中间，可以根据启发函数的好坏在两者之间自由滑动。
本节小结
如果只让你记住一句话，那就是：A* 用 $f(n) = g(n) + h(n)$ 来给每个节点估一个“全程总账”，其中 $g$ 是从起点到这里已经实付的真实代价（已花的钱），$h$ 是从这里到目标预估还要付的启发式代价（预估还要花的钱），A* 每一步都从优先队列里挑总账 $f$ 最小的节点优先探索。$g$ 让它最优，$h$ 让它高效；$h$ 归零它就是 Dijkstra，丢掉 $g$ 它就是贪心，而把两者相加，就得到了既稳又快的 A*。
算法细节：open/closed、优先队列、伪代码、在网格上走一遍
前面我们已经知道 A* 的核心是用 $f(n)=g(n)+h(n)$ 这个估价函数（evaluation function）来给节点排序：$g(n)$ 是从起点到节点 $n$ 已经确实走过的代价（cost-so-far），$h(n)$ 是从 $n$ 到目标的启发式估计（heuristic）。现在我们要把这套思想落到可以真正执行的流程上，看清楚每一步到底维护了哪些数据、做了什么判断。
两张表：open list 与 closed list
A* 在运行过程中，把所有节点划分到三种状态里，由两张表来管理。
第一张是 open list（开放列表，又叫边界 frontier）。它装的是「已经被发现、但还没有被最终确定」的节点，也就是「待扩展」的候选。这张表是 A* 的引擎，它本质上是一个优先队列（priority queue），按 $f$ 值从小到大排序。每一轮，A* 都从 open list 里取出 $f$ 最小的那个节点来处理。直觉上，$f$ 最小意味着「这个节点看起来最有希望落在最短路径上」（已花代价 + 预计还要花的代价之和最小），所以优先去看它。
第二张是 closed list（关闭列表，又叫已访问集合）。它装的是「已经被取出、扩展完毕、最优代价已经定下来」的节点。一旦一个节点进了 closed list，我们就认为「从起点到它的最短代价已经找到了，不必再回头处理它」。注意：这个「不必回头」的保证，依赖于启发式 $h$ 满足一致性（consistency，又叫单调性 monotonicity）；如果 $h$ 只是可采纳（admissible）而不一致，那么一个已经进 closed list 的节点，理论上仍可能在后面被发现更短的路径，需要被重新打开（re-open）。本节先按「一致启发式」的常见情形来讲，这样 closed list 一旦确定就不再变动，流程最清爽。
第三种状态是「尚未被发现的节点」，它们既不在 open 也不在 closed 里，A* 还没碰到过它们。
每个节点要记住两件东西：$g$ 值与父指针
光有两张表还不够。对每一个已经被发现的节点 $n$，我们还要为它存两份信息。
一是 $g(n)$，即「目前已知的、从起点到 $n$ 的最小代价」。注意「目前已知」这个限定词：在一致启发式下，节点一旦出 open 进 closed，$g(n)$ 就是真正的最短代价；但在它还待在 open list 里时，$g(n)$ 只是「到现在为止找到的最好值」，后面还可能被更新得更小。
二是 父指针（parent / came-from），记录「在当前已知最优路径上，$n$ 的前一个节点是谁」。这个指针是用来回溯路径（path reconstruction）的：等找到目标后，我们从目标顺着父指针一路倒推回起点，再反转过来，就得到完整路径。可以把父指针理解成：每个节点都记着「我这条最划算的路，是从哪个邻居走过来的」。
松弛：更新邻居的核心动作
A* 每次取出一个节点 $u$（称为「扩展 $u$」）之后，要做的事是遍历 $u$ 的所有邻居 $v$，尝试「经过 $u$ 去到 $v$ 是不是更划算」。这一步叫松弛（relaxation），是从最短路算法（如 Dijkstra）继承来的概念。
具体地，设 $u$ 到 $v$ 的边代价为 $c(u,v)$，则「经过 $u$ 到达 $v$ 的候选代价」为：
\[g_{\text{new}} = g(u) + c(u,v)\]然后比较 $g_{\text{new}}$ 和 $v$ 目前已知的 $g(v)$：
- 如果 $v$ 从没被发现过，或者 $g_{\text{new}} < g(v)$（找到了更短的到 $v$ 的路），那么就松弛成功：把 $g(v)$ 更新为 $g_{\text{new}}$，把 $v$ 的父指针指向 $u$，重新算出 $f(v)=g(v)+h(v)$，并把 $v$ 放进（或在优先队列里更新位置 / 重新插入）open list。
- 否则（经过 $u$ 并没有更划算），什么都不做，保持 $v$ 原样。
「松弛」这个词的画面感是：把一条原本绷得太长的路径「放松」拉短。每成功松弛一次，某个节点到起点的已知距离就缩短一点。
目标判定与回溯
A* 的终止判定是：当目标节点被从 open list 中取出（即将被扩展）的那一刻，算法成功结束。请特别注意，是「被取出时」判定，而不是「被发现 / 被放进 open 时」判定。原因在于：一个节点第一次被放进 open list 时，它的 $g$ 值可能还不是最优；只有当它以最小 $f$ 被弹出时，在可采纳（且一致）启发式下，才能保证此时的 $g$ 就是从起点到它的真正最短代价。若在「刚发现目标」时就停，可能得到一条比最优解更长的路径。
结束后，从目标顺着父指针回溯到起点，反转即得最短路径；此时的 $g(\text{goal})$ 就是最短路径的总代价。如果 open list 被取空了还没碰到目标，说明目标不可达（unreachable），返回失败。
伪代码
下面给出完整流程的伪代码。为简洁起见，把「检查 $v$ 是否在 open / closed 中」「在优先队列里更新 $v$ 的优先级」这类操作写成抽象动作；实际实现里，open list 常用二叉堆（binary heap）配合一个哈希表（记录每个节点当前的最好 $g$）来做。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
function A_Star(start, goal, h):
# g[n]：起点到 n 的当前最优已知代价；默认无穷大
# parent[n]：n 在当前最优路径上的前驱
g <- map with default value +infinity
parent <- empty map
g[start] <- 0
f_start <- g[start] + h(start) # = h(start)，因为 g[start]=0
open <- empty priority queue ordered by f # 优先队列，按 f 从小到大
open.push(start, priority = f_start)
closed <- empty set # 已确定节点集合
while open is not empty:
u <- open.pop_min() # 取出 f 最小的节点
if u == goal: # 关键：在“取出时”判定目标
return reconstruct_path(parent, goal), g[goal]
if u in closed: # 一致启发式下可省略；用惰性删除时需要
continue
closed.add(u)
for each neighbor v of u:
if v in closed: # 已确定的节点不再处理（一致启发式）
continue
g_new <- g[u] + cost(u, v) # 经过 u 到 v 的候选代价
if g_new < g[v]: # 松弛：找到更短的到 v 的路
g[v] <- g_new
parent[v] <- u
f_v <- g_new + h(v)
open.push(v, priority = f_v) # 插入或更新 v 的优先级
return failure # open 取空仍未到达 goal：目标不可达
function reconstruct_path(parent, goal):
path <- empty list
node <- goal
while node is defined:
path.prepend(node) # 头插，等价于最后反转
node <- parent[node] # 顺父指针倒推
return path # 从 start 到 goal 的节点序列
几点工程说明：（1）很多堆实现不支持「降低优先级（decrease-key）」操作，所以这里用的是「直接再 push 一份新的 $(v, f_v)$」的惰性删除（lazy deletion）策略，同一个 $v$ 可能在堆里有多份旧记录；弹出时若发现 $u$ 已在 closed 里，就 continue 跳过它，这就是伪代码里那行 if u in closed 的作用。（2）cost(u,v) 在均匀网格里通常取 $1$（四连通）或对角线取 $\sqrt 2$（八连通）。（3）h 由调用者给定，它的好坏直接决定 A* 扩展多少节点。
在一个小网格上走一遍
光看伪代码还是抽象，下面用一个 $5\times 5$ 的小网格把 A* 跑起来，亲眼看它如何「朝目标定向扩展」。
| 设定如下。坐标记为 $(x,y)$，$x$ 是列、$y$ 是行，左上角为 $(0,0)$。允许上下左右四个方向移动（四连通），每走一步代价为 $1$。起点 $S=(0,0)$，目标 $G=(4,0)$。中间放一道竖墙障碍：格子 $(2,0)$、$(2,1)$、$(2,2)$ 不可通行，逼迫路径绕行。启发式用曼哈顿距离（Manhattan distance） $h\big((x,y)\big)= | x-4 | + | y-0 | $，它在四连通、每步代价 $1$ 的网格上既可采纳又一致，是这类问题的标准选择。 |
网格示意（S 起点，G 目标，# 障碍，. 可通行）：
1
2
3
4
5
6
x=0 x=1 x=2 x=3 x=4
y=0 S . # . G
y=1 . . # . .
y=2 . . # . .
y=3 . . . . .
y=4 . . . . .
我们一步步看，每个格子标注 $g\,/\,h\,/\,f$。
初始化。 $g(S)=0$，$h(S)=|0-4|+|0-0|=4$，故 $f(S)=0+4=4$。 open $={\,S(f{=}4)\,}$，closed $=\varnothing$。
第 1 轮：扩展 $S=(0,0)$。 它是 open 里 $f$ 最小（也是唯一）的。$S$ 不是目标，放入 closed。它的邻居有 $(1,0)$ 和 $(0,1)$（向上、向左越界，右边 $(1,0)$ 在格内）。两个邻居各自松弛：
$(1,0)$：$g=0+1=1$，$h= 1-4 +0=3$，$f=1+3=4$。父指针 $\to S$。 $(0,1)$：$g=0+1=1$，$h= 0-4 +1=5$，$f=1+5=6$。父指针 $\to S$。
open $={\,(1,0)!:!f{=}4,\ (0,1)!:!f{=}6\,}$，closed $={S}$。
请注意此刻的关键现象：两个邻居 $g$ 相同（都是 $1$），但 $(1,0)$ 朝着目标方向（向右），它的 $h$ 更小，于是 $f$ 更小，排到了队首。这正是 $h$ 在起作用：它让 A* 偏向目标，而不像 Dijkstra 那样向四面八方均匀膨胀。
| 第 2 轮：扩展 $(1,0)$（$f=4$，队首）。 放入 closed。邻居有 $(0,0)=S$（已在 closed，跳过）、$(2,0)$（障碍，跳过）、$(1,1)$。松弛 $(1,1)$：$g=1+1=2$，$h= | 1-4 | +1=4$，$f=2+4=6$，父 $\to(1,0)$。 |
向右的 $(2,0)$ 撞墙了，A* 在这里第一次「感受」到障碍。 open $={\,(0,1)!:!f{=}6,\ (1,1)!:!f{=}6\,}$，closed $={S,(1,0)}$。
第 3 轮：扩展 $f=6$ 的节点（$(0,1)$ 与 $(1,1)$ 并列）。 并列时按实现的 tie-breaking 规则任选其一；常见做法是优先选 $h$ 更小（更靠近目标）的，这里 $(1,1)$ 的 $h=4$ 小于 $(0,1)$ 的 $h=5$，所以先取 $(1,1)$。放入 closed。它的邻居：$(1,0)$（closed，跳过）、$(0,1)$、$(2,1)$（障碍，跳过）、$(1,2)$。
- $(0,1)$：经 $(1,1)$ 的候选 $g=2+1=3$，但 $(0,1)$ 现有 $g=1$，$3<1$ 不成立，松弛失败，不更新。（A* 没有被引诱去走更绕的路。）
$(1,2)$：$g=2+1=3$，$h= 1-4 +2=5$，$f=3+5=8$，父 $\to(1,1)$。
open $={\,(0,1)!:!f{=}6,\ (1,2)!:!f{=}8\,}$，closed $={S,(1,0),(1,1)}$。
第 4 轮：扩展 $(0,1)$（$f=6$）。 放入 closed。邻居 $(0,0)$（closed）、$(1,1)$（closed）、$(0,2)$。松弛 $(0,2)$：$g=1+1=2$，$h=|0-4|+2=6$，$f=2+6=8$，父 $\to(0,1)$。 open $={\,(1,2)!:!f{=}8,\ (0,2)!:!f{=}8\,}$，closed 再添 $(0,1)$。
| 第 5 轮起：沿墙下行、绕过墙脚。 此后 $f=8$ 的一批节点（$(1,2)$、$(0,2)$ 等）被陆续扩展。由于第 2、3 列上半部分被墙堵死，A* 被迫沿着第 1 列、第 0 列往下走，直到走到墙的下边缘 $y=3$ 这一行（$(2,2)$ 是障碍，但 $(2,3)$ 是通的）。我们重点看「绕过墙脚」的那一步：当扩展到 $(1,3)$ 后（它的 $g$ 沿着 $S\to(1,0)\to(1,1)\to(1,2)\to(1,3)$ 累加为 $4$），松弛右邻 $(2,3)$：$g=4+1=5$，$h= | 2-4 | +3=5$，$f=5+5=10$。墙脚被绕过，路径终于得以向右穿过第 2 列。 |
收尾：穿过墙后径直奔向目标。 过了 $(2,3)$ 之后，前方再无障碍，曼哈顿启发式会持续把 A* 往右上方的目标 $G=(4,0)$ 牵引。沿着 $(2,3)\to(3,3)\to(3,2)\to(3,1)\to(3,0)\to(4,0)$ 这条向右、再向上的路线，$g$ 一路累加，$f$ 始终贴着「真实最短代价」。当 $G=(4,0)$ 终于以最小 $f$ 被弹出 open list 时，算法停止。
回溯父指针，得到一条最短路径（其中一条最优解，长度为 $10$ 步）：
1
2
(0,0) -> (1,0) -> (1,1) -> (1,2) -> (1,3) -> (2,3)
-> (3,3) -> (3,2) -> (3,1) -> (3,0) -> (4,0)
最终路径在网格上的样子（* 标记路径）：
1
2
3
4
5
6
x=0 x=1 x=2 x=3 x=4
y=0 S * # * G
y=1 . * # * .
y=2 . * # * .
y=3 . * * * .
y=4 . . . . .
从这一遍走查里要带走的直觉。 第一，A* 始终「优先处理 $f$ 最小的节点」，而 $f=g+h$ 里的 $h$ 项把搜索拧向目标，使得扩展像「有方向的水流」而非「均匀扩散的墨滴」；越靠近目标方向的节点 $f$ 越小、越早被处理。第二，松弛保证了每个节点记录的都是「目前已知最短」的 $g$ 和对应父指针，所以一旦目标被弹出，顺父指针回溯就能拿到货真价实的最短路径。第三，障碍并不需要任何特殊逻辑，它只是让某些邻居「不存在」（不可松弛），A* 会自然地沿着可行邻居绕开，并因为启发式的牵引而尽量贴着墙、走最短的绕行路线。第四，正因为用了启发式，A* 在到达目标前几乎没有去探索那些明显偏离目标的格子（比如左下角的 $(0,4)$ 一带在本例中根本没被扩展），这就是它比无信息的 Dijkstra 高效的根本原因。
为什么最优：可采纳性、一致性与最优性证明
在介绍完 A* 的基本机制（用 $f(n)=g(n)+h(n)$ 来排序待扩展节点）之后，一个最自然的问题是：A* 找到的真的是最短路径吗？答案是：在启发函数（heuristic function）$h$ 满足某些条件时，是的。这一节我们就把这件事讲清楚。我们会区分两个层次的条件，可采纳性（admissibility）和一致性（consistency），说明它们各自保证什么，并给出直觉清晰、又经得起推敲的证明。
先约定符号
为了后面讲得严谨，我们先把记号统一一下。
- $g(n)$：从起点到节点 $n$ 的当前已知路径代价（cost），也就是搜索过程中记录下来的、走到 $n$ 的那条路的长度。注意它会随搜索更新，不一定是最优的。
- $g^\ast(n)$：从起点到 $n$ 的真实最短代价。这是一个客观存在的量，与算法无关。
- $h(n)$：启发函数，是我们对“从 $n$ 到目标还要走多远”的估计。
- $h^\ast(n)$：从 $n$ 到目标的真实最短剩余代价。同样是客观量。
- $f(n)=g(n)+h(n)$：A* 用来排序的估值。
- $f^\ast(n)=g^\ast(n)+h^\ast(n)$：经过 $n$ 的最优路径的真实总代价。
- $c(n,n’)$：从 $n$ 到其相邻节点 $n’$ 的一步边代价（edge cost），假设它总是非负的。
直觉上，$h$ 是“猜测”，$h^\ast$ 是“真相”。A* 好不好，关键就在于 $h$ 这个猜测和 $h^\ast$ 这个真相之间是什么关系。
第一个条件：可采纳性（admissible）
定义：称启发函数 $h$ 是可采纳的，如果对所有节点 $n$ 都有
\[h(n) \le h^\ast(n).\]用一句话说：可采纳就是从不高估（never overestimate）真实剩余代价。它可以低估（猜得偏小），可以正好（猜得精准），但绝不能猜得比真相还大。
为什么“从不高估”这件事如此关键？给一个生活化的直觉。假设你在找回家的最短路，手里有一个“乐观的估价器”，它对每个路口都告诉你“从这里到家最多还要这么远”，而且它给的数从不超过实际还要走的路。那么当这个估价器说“经过某个路口回家，总代价看起来很大”时，你可以放心相信：真实代价只会更大，不会更小。换句话说，乐观的估计不会骗你去过早放弃一条其实很短的路。正是这种“乐观永不误导”的性质，保证了 A* 不会错过最优解。
一个极端的特例能帮助理解：取 $h(n)\equiv 0$，这显然满足 $0\le h^\ast(n)$（剩余代价非负），所以它是可采纳的。此时 $f(n)=g(n)$，A* 就退化成了 Dijkstra 算法。Dijkstra 本来就保证最优，这和我们下面的结论一致，可采纳的 $h=0$ 给出最优解。常用的可采纳启发例子还有：网格地图上的曼哈顿距离（Manhattan distance）或欧几里得距离（Euclidean distance），只要它们不会超过实际要走的步数，就都是合法的乐观估计。
可采纳性保证 A*（树搜索版本）最优
我们要证明的命题是：如果 $h$ 可采纳，那么当 A*（树搜索，tree search，即不去重、允许同一状态多次进入边缘队列）扩展到目标节点并返回时，返回的解是最优的。
这里的“树搜索”是关键限定。所谓树搜索，是指我们不维护已访问集合（closed list），把搜索空间当成一棵展开的树来探索，同一个状态可能沿不同路径被反复加入边缘队列（frontier，也叫 open list）。在这种设定下，仅凭可采纳性就够了。
证明的思路是反证法。我们先建立一个核心引理，再用它推出结论。
第一步，先看一个对最优路径上的节点成立的不等式。设目标为 $G$，最优解代价为 $C^\ast=g^\ast(G)$。对最优路径上任意一个尚在边缘队列里的节点 $n$，因为它在最优路径上，所以走到它的最优代价加上它到目标的最优剩余代价正好等于总最优代价：
\[g^\ast(n) + h^\ast(n) = C^\ast.\]又因为树搜索沿最优路径走到 $n$ 时，$g(n)$ 不会比最优更小（边代价非负，记录的路径长度至少是 $g^\ast(n)$；在最优路径上的那份记录恰好等于 $g^\ast(n)$）。取最优路径上那条记录，结合可采纳性 $h(n)\le h^\ast(n)$，得到
\[f(n) = g(n) + h(n) = g^\ast(n) + h(n) \le g^\ast(n) + h^\ast(n) = C^\ast.\]这说明一个重要事实：只要最优路径还没走完，最优路径上总有一个边缘节点 $n$，它的 $f(n)\le C^\ast$。也就是说，边缘队列里始终“埋伏”着一个估值不超过最优代价的节点。
第二步，反证。假设 A* 返回了一个次优的目标节点 $G_2$，它对应的路径代价 $g(G_2)>C^\ast$。因为 $G_2$ 是目标，到目标的剩余代价为零，$h(G_2)=0$（合理的启发对目标取零），所以
\[f(G_2) = g(G_2) + 0 = g(G_2) > C^\ast.\]A* 是按 $f$ 从小到大扩展的，它选择扩展 $G_2$ 说明此刻 $G_2$ 的 $f$ 值是边缘队列里最小的。但由第一步我们知道，队列里还有最优路径上的某个节点 $n$ 满足 $f(n)\le C^\ast < f(G_2)$。这就矛盾了：既然 $n$ 的 $f$ 更小，A* 应该先扩展 $n$（从而沿最优路径推进），而不会先把次优的 $G_2$ 拿出来当作答案返回。
矛盾说明假设不成立，因此 A* 返回的目标节点代价不可能超过 $C^\ast$，即返回的就是最优解。证毕。
这个证明的精髓在于：可采纳性让 $f(n)$ 成为最优总代价的一个下界（lower bound），$f(n)\le f^\ast(n)$。于是任何一个真实代价超过 $C^\ast$ 的目标，都会“排在”最优路径节点的后面被处理，A* 不可能提前以次优解收场。
为什么树搜索还不够：重复状态的隐患
上面的证明对树搜索成立。但实际中我们几乎总会用图搜索（graph search），也就是维护一个已访问集合 closed list，一旦某个状态被扩展过，就不再重复扩展，以避免在有环或有大量重复路径的图里反复打转。
问题来了：仅有可采纳性，图搜索可能出错。原因是，A* 第一次把某个状态 $n$ 放进 closed list 时，所走的那条路径不一定是到 $n$ 的最优路径。如果之后又发现一条更短的路通向 $n$，但 $n$ 已经被关闭、不再扩展，那么这条更优的路就被错误地丢弃了，最终可能导致整体解次优。可采纳性只约束了 $h$ 和 $h^\ast$ 的关系，并没有保证“第一次到达每个节点就是最优到达”，所以树搜索的论证在这里断裂。
要修补这个漏洞，有两条路。其一是在图搜索中允许“重新打开”（reopening），即当发现到某个已关闭节点的更短路径时，把它从 closed list 里拿出来重新处理。其二，也是更优雅的办法，是给 $h$ 加上更强的条件，让“第一次到达即最优到达”自动成立。这就引出了一致性。
第二个条件：一致性 / 单调性（consistent / monotone）
定义：称启发函数 $h$ 是一致的，如果对每条边 $(n,n’)$ 都有
\[h(n) \le c(n,n') + h(n'),\]并且对目标节点 $G$ 有 $h(G)=0$。
这个不等式长得很像三角不等式（triangle inequality），事实上它就是启发函数版本的三角不等式：“从 $n$ 直接估到目标”不应该比“先花 $c(n,n’)$ 走到邻居 $n’$、再从 $n’$ 估到目标”更大。直觉上，它要求启发函数的估计在相邻节点之间“变化平滑、不跳跃”，每走一步，对剩余代价的估计下降不超过这一步实际花的代价。
之所以又叫“单调性”，是因为它等价于：沿任意一条路径，$f$ 值不会下降（non-decreasing）。我们验证一下这个等价表述。设 $n’$ 是 $n$ 的后继，路径上 $g(n’)=g(n)+c(n,n’)$，于是
\[f(n') = g(n') + h(n') = g(n) + c(n,n') + h(n') \ge g(n) + h(n) = f(n),\]其中不等号正好用到了一致性 $c(n,n’)+h(n’)\ge h(n)$。所以一致性 $\iff$ 沿路径 $f$ 单调不减。这个“$f$ 单调不减”的性质，正是图搜索最优性的关键。
一致性保证 A*（图搜索，带 closed list）最优，且每个节点至多扩展一次
我们证明两个相关的结论。
结论一（第一次扩展即最优）：如果 $h$ 一致，那么当 A* 第一次扩展（从边缘队列取出）某个节点 $n$ 时，此时记录的 $g(n)$ 就等于真实最短代价 $g^\ast(n)$。
证明的核心是：A* 在一致启发下，是按 $f$ 值非降的顺序扩展节点的。为什么是非降顺序？设算法刚扩展了节点 $n$，把它的后继 $n’$ 加入队列。由单调性，$f(n’)\ge f(n)$，也就是说新产生的节点 $f$ 值不会比刚被取出的 $n$ 更小。再加上优先队列总是取出当前 $f$ 最小的节点，可以归纳地证明：被依次扩展的节点序列，其 $f$ 值单调不减。
有了“按 $f$ 非降扩展”，再证结论一。反证：假设第一次扩展 $n$ 时 $g(n)>g^\ast(n)$，即存在一条更短的路到 $n$ 尚未被走完。沿这条最优路径，必有一个已在队列里、但还没被扩展的节点 $m$（它是最优路径上第一个“还没扩展”的节点）。在最优路径上，$g(m)=g^\ast(m)$（它前面的节点都已最优扩展），所以
\[f(m) = g^\ast(m) + h(m).\]由一致性可推出 $h$ 也可采纳（下面会单独证明这点），故 $h(m)\le h^\ast(m)$，于是
\[f(m) = g^\ast(m) + h(m) \le g^\ast(m) + h^\ast(m) = f^\ast(n) \le g(n) + h(n) = f(n),\]最后一步用到 $g(n)>g^\ast(n)$ 推出 $f^\ast(n)=g^\ast(n)+h^\ast(n)\le g^\ast(n)+h(n)<g(n)+h(n)=f(n)$（这里再次用了可采纳 $h\le h^\ast$ 与 $g(n)>g^\ast(n)$）。结果 $f(m)<f(n)$，说明 $m$ 应当先于 $n$ 被扩展，与“现在正在第一次扩展 $n$”矛盾。所以第一次扩展 $n$ 时必有 $g(n)=g^\ast(n)$。证毕。
结论二（每个节点至多扩展一次）：由结论一，A* 第一次扩展 $n$ 时拿到的就是最优 $g^\ast(n)$，之后不可能再发现更短的路径到 $n$，因而没有任何理由重新打开它。于是把 $n$ 放进 closed list、永不再扩展，是完全安全的，每个节点至多被扩展一次。这既保证了正确性，也给出了效率上的好处：避免了重复打开带来的额外开销，使图搜索版 A* 的扩展次数有了清晰上界。
把两点合起来：一致性下，图搜索 A* 对每个节点第一次到达即最优、每个节点只扩展一次，最终到达目标时 $g(G)=g^\ast(G)=C^\ast$，返回的就是最优解。
一致必可采纳，反之不一定
最后澄清这两个条件的强弱关系，这常常是初学者困惑的地方。结论是：一致性比可采纳性强，一致 $\Rightarrow$ 可采纳，但可采纳不一定一致。
先证一致 $\Rightarrow$ 可采纳。 我们要证明：若 $h$ 一致且 $h(G)=0$，则对所有 $n$ 有 $h(n)\le h^\ast(n)$。思路是沿从 $n$ 到目标的最优路径逐边累加一致性不等式。设从 $n$ 到目标 $G$ 的最优路径为 $n=n_0\to n_1\to\cdots\to n_k=G$，它的总代价就是 $h^\ast(n)=\sum_{i=0}^{k-1} c(n_i,n_{i+1})$。对每条边写出一致性：
\[h(n_i) \le c(n_i,n_{i+1}) + h(n_{i+1}).\]把这 $k$ 个不等式从 $i=0$ 到 $k-1$ 依次叠加（链式代入），中间的 $h(n_1),\dots,h(n_{k-1})$ 逐层抵消，得到
\[h(n_0) \le \sum_{i=0}^{k-1} c(n_i,n_{i+1}) + h(n_k) = h^\ast(n) + h(G) = h^\ast(n) + 0 = h^\ast(n).\]即 $h(n)\le h^\ast(n)$，可采纳性成立。证毕。这个推导也解释了一致性为什么更“强”：它不仅在“整条最优路径”这个全局尺度上不高估（那是可采纳），而且在“每一步”这个局部尺度上都不高估，逐边的局部约束累加起来自然蕴含了全局约束。
再说明反之不一定。 存在可采纳但不一致的启发函数。给一个直观的构造。考虑两个相邻节点 $n$ 和 $n’$，边代价 $c(n,n’)=1$。设真实剩余代价为 $h^\ast(n)=3$、$h^\ast(n’)=2$。取 $h(n)=3$（等于真相，合法不高估）、$h(n’)=0$（远低于真相，更不高估）。逐个看可采纳性：$h(n)=3\le 3$、$h(n’)=0\le 2$，两者都满足，所以 $h$ 是可采纳的。但检查一致性：
\[h(n) = 3 \quad\text{vs.}\quad c(n,n') + h(n') = 1 + 0 = 1,\]而 $3 > 1$，违反了 $h(n)\le c(n,n’)+h(n’)$。所以这个 $h$ 可采纳却不一致。直觉上，问题出在估计在相邻两点之间“跳变”太剧烈：从 $n$ 到 $n’$ 只走了 1 步，启发值却从 3 暴跌到 0，下降幅度远超这一步的实际代价。可采纳只管“不高估总剩余”，并不在乎相邻估计是否平滑，所以允许这种突变；而一致性恰恰禁止这种突变。
正因如此，可采纳但不一致的启发用在图搜索时，可能出现“某节点先以次优路径被关闭、后来才发现更短路径”的情况，此时若不做重新打开，结果可能次优。这再次印证了前面的论断：图搜索要安全省心，最好用一致启发；只有可采纳时，要么退回树搜索，要么在图搜索中允许重新打开。
小结与速记表
把这一节的结论浓缩成一张对照表，方便记忆。
| 条件 | 数学定义 | 直觉 | 保证什么 |
|---|---|---|---|
| 可采纳（admissible） | $h(n)\le h^\ast(n)$ | 从不高估总剩余代价（全局乐观） | A* 树搜索最优 |
| 一致（consistent） | $h(n)\le c(n,n’)+h(n’)$，且 $h(G)=0$ | 每一步估计平滑，沿路径 $f$ 单调不减（局部乐观） | A* 图搜索（带 closed list）最优，且每个节点至多扩展一次 |
三句话记牢这一节：
- 可采纳是“乐观永不误导”，它让 $f(n)=g(n)+h(n)$ 成为最优代价的下界，从而保证 A* 树搜索不会以次优解收场。
- 一致是更强的“逐步乐观”，等价于沿路径 $f$ 单调不减，从而第一次扩展某节点就是最优到达，使带 closed list 的图搜索安全、且每个节点只扩展一次。
- 一致必可采纳（逐边不等式累加即得），可采纳不一定一致（估计可以在相邻节点间剧烈跳变）。实践中如果用图搜索，优先设计一致的启发函数。
启发式怎么设计:曼哈顿、欧氏、切比雪夫与支配性
前面我们知道,A* 的排序键是 $f(n) = g(n) + h(n)$,其中 $g(n)$ 是从起点到当前节点 $n$ 已经走过的真实代价,$h(n)$ 是从 $n$ 到终点的估计代价。$h$ 就是启发式函数（heuristic function）。它是 A* 的灵魂:换一个 $h$,算法的快慢、甚至最优性,都会跟着变。这一节我们就来回答一个很实际的问题:面对一张具体的网格地图，到底该把 $h$ 写成什么样？
我们一步一步来。先回顾两个关键性质，因为后面所有讨论都绕着它们转。
先把两个性质摆在台面上
启发式 $h$ 好不好，主要看两个性质。
第一个是可采纳性（admissibility），也叫不高估（never overestimate）。记 $h^\ast(n)$ 为从 $n$ 到终点的真实最短代价（理论上的、考虑了所有障碍的那个真值）。可采纳的定义是:
\[h(n) \le h^\ast(n) \quad \text{对所有节点 } n\]也就是说，你的估计永远不超过真实值，宁可保守，绝不夸大。A* 在 $h$ 可采纳时，保证找到最优解。 直觉上原因是:如果 $h$ 不高估，那么当 A* 把终点从优先队列里弹出时，它已经确信没有别的路径能更短，因为所有还没探索的方向的 $f$ 值都不会被低估到“看起来更近却其实更远”。一旦 $h$ 在某处高估了（说“这条路只要 5”，实际要 10），A* 可能会被骗着提前认定一条次优路径是最优的，于是返回错误答案。
第二个是一致性（consistency），也叫单调性（monotonicity）。它比可采纳性更强，要求对任意相邻节点 $n$ 和 $n’$（设从 $n$ 走到 $n’$ 的边代价为 $c(n, n’)$）满足三角不等式:
\[h(n) \le c(n, n') + h(n')\]一致性保证 $f$ 值沿路径单调不减，于是 A* 在闭集（closed set）里每个节点只需展开一次，不用反复回炉。好消息是:本节要讲的曼哈顿、欧氏、切比雪夫这几个标准距离，在对应的网格上都是一致的（因此自动也是可采纳的），所以我们可以放心使用，不必担心一致性这个更细的坑。
记住这条主线:我们要的 $h$ 是“在不高估的前提下，尽量大、尽量贴近 $h^\ast$”。 为什么要尽量大，下面讲支配性时会严格说清楚。
常见启发式之一:曼哈顿距离（Manhattan distance，四连通）
设当前节点坐标 $(x_1, y_1)$，终点坐标 $(x_2, y_2)$。曼哈顿距离是:
\[h_{\text{man}} = |x_1 - x_2| + |y_1 - y_2|\]它的名字来自曼哈顿街区:街道横平竖直，你不能斜穿建筑，只能沿着横向和纵向的街道走，总路程就是横向格数加纵向格数。
| 什么时候可采纳？ 当智能体只能上下左右移动（四连通，4-connectivity）、且每步代价相同（设为 $1$）时，曼哈顿距离恰好等于“没有障碍时的真实最短步数”。因为在四连通下，你横向至少要走 $ | x_1 - x_2 | $ 步、纵向至少要走 $ | y_1 - y_2 | $ 步，缺一不可，加起来就是下界。有障碍时真实路径只会更长，所以 $h_{\text{man}} \le h^\ast$，可采纳成立。 |
陷阱:不要在允许斜走的地图上用曼哈顿距离。 如果地图实际允许八方向移动（斜着一步就能同时改变 $x$ 和 $y$），那么从 $(0,0)$ 到 $(3,3)$ 真实只要 $3$ 步（一直斜走），而曼哈顿距离给出 $6$。$6 > 3$，这就高估了，可采纳性被破坏，A* 可能返回非最优路径。所以“连通方式”和“启发式”必须配套。
常见启发式之二:欧氏距离（Euclidean distance）
欧氏距离就是我们日常说的“直线距离”，由勾股定理给出:
\[h_{\text{euc}} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\]它表示“如果可以无视网格、笔直飞过去”的最短距离。
什么时候可采纳？ 几乎总是可采纳，因为任何在网格上行走的路径长度都不可能短于两点间的直线距离（直线是平面上两点间最短路径，这是几何学的基本事实）。所以无论四连通、八连通，甚至允许任意角度移动，都有 $h_{\text{euc}} \le h^\ast$。
它的代价是什么？ 正因为它“太通用”，在只能上下左右走的网格上，它往往偏小、过于乐观。例如四连通下从 $(0,0)$ 到 $(3,3)$，真实要 $6$ 步，曼哈顿给出准确的 $6$，而欧氏只给 $\sqrt{18} \approx 4.24$。估计值越小，越接近 Dijkstra，扩展的节点越多、越慢（原因见支配性）。所以“可采纳”不等于“好用”，欧氏距离常常因为太保守而效率偏低。此外它带根号，是浮点数，比较时还要小心数值误差。
常见启发式之三:切比雪夫距离（Chebyshev distance，八连通）
| 设两个方向的差为 $dx = | x_1 - x_2 | $、$dy = | y_1 - y_2 | $。切比雪夫距离是: |
它对应八连通（8-connectivity）、且斜走与直走代价相同（都记为 $1$）的情形。直觉:每走一步，斜着可以同时把 $x$ 和 $y$ 各推进 $1$。所以你可以先用斜步把“较短的那个方向”消耗掉，剩下的再用直步走完，总步数恰好是较长的那一边 $\max(dx, dy)$。例如从 $(0,0)$ 到 $(3,1)$:先斜走 $1$ 步到 $(1,1)$，再直走 $2$ 步到 $(3,1)$，共 $3$ 步 $= \max(3,1)$。
什么时候可采纳？ 当且仅当移动模型是“八连通、斜直同价”时，切比雪夫距离等于无障碍真实步数，可采纳且一致。
一个常被忽略的细节:对角线距离（octile / diagonal distance）。 很多游戏里斜走一步的真实代价是 $\sqrt{2}$（因为它走的物理距离更长），而不是 $1$。这时切比雪夫就偏小（它把斜步当成 $1$）。正确做法是把斜步代价记为 $\sqrt{2}$，启发式改用对角线距离:
\[h_{\text{oct}} = (dx + dy) + (\sqrt{2} - 2)\min(dx, dy)\]| 它的含义是:先用 $\min(dx, dy)$ 个对角步（每步代价 $\sqrt{2}$）走掉斜向部分，再用剩下的 $ | dx - dy | $ 个直步走完。这是八连通斜直不同价时的精确、可采纳启发式。 |
把上面四种整理成一张速查表（设每条直边代价为 $1$）:
| 启发式 | 公式 | 适配的移动模型 | 何时可采纳 |
|---|---|---|---|
| 曼哈顿 Manhattan | $dx + dy$ | 四连通（上下左右） | 仅四连通、单位代价时；允许斜走会高估 |
| 欧氏 Euclidean | $\sqrt{dx^2 + dy^2}$ | 任意角度 / 通用 | 几乎总可采纳；在格子地图上常偏保守 |
| 切比雪夫 Chebyshev | $\max(dx, dy)$ | 八连通、斜直同价 | 仅斜直同价时精确；斜步若更贵会偏小 |
| 对角线 Octile | $(dx+dy)+(\sqrt 2 - 2)\min(dx,dy)$ | 八连通、斜步代价 $\sqrt 2$ | 八连通斜直不同价时精确 |
一句话记忆:选启发式的第一步，永远是先看“智能体怎么动、每种动作多少代价”，再挑那个“无障碍时算得准、且不会高估”的距离。
支配性:为什么“启发式越大越好”
现在回到最核心的问题:同样都可采纳，曼哈顿和欧氏到底选谁？答案藏在支配性（dominance）里。
定义很简单。设 $h_1$ 和 $h_2$ 都是可采纳启发式。如果对所有节点 $n$ 都有:
\[h_2(n) \ge h_1(n)\]我们就说 $h_2$ 支配（dominate）$h_1$，或者说 $h_2$ 更“有信息量（more informed）”。
核心定理（直觉版）:在 $h_2$ 支配 $h_1$ 的前提下，用 $h_2$ 跑 A* 所展开的节点集合，是用 $h_1$ 展开的节点集合的子集（在合理的 tie 处理下）。换句话说，$h_2$ 永远不会比 $h_1$ 多探索，通常还少探索很多。 所以支配性高的启发式更高效。
为什么会这样？给一个能站得住脚的直觉论证。A* 的一个经典结论是:任何 $f(n) < C^\ast$ 的节点都必然会被展开（这里 $C^\ast$ 是最优解的总代价）。把 $f$ 拆开看:
\[f(n) = g(n) + h(n)\]对同一个节点 $n$，$g(n)$ 与启发式无关。$h$ 越大，$f(n) = g(n) + h(n)$ 就越大，就越容易超过门槛 $C^\ast$，于是这个节点就越不会被展开。因为 $h_2 \ge h_1$，凡是被 $h_2$ 展开（即 $g + h_2 < C^\ast$）的节点，必然也满足 $g + h_1 \le g + h_2 < C^\ast$，从而也会被 $h_1$ 展开。反过来不成立。所以 $h_2$ 展开的节点是 $h_1$ 的子集。少展开节点，就意味着更少的入队出队、更快的搜索。
把这个图景推到两个极端，理解就完整了:
- $h = 0$:最弱的可采纳启发式。 它对所有节点都成立 $0 \le h^\ast$，是合法的，但毫无信息量。此时 $f(n) = g(n)$，A* 退化成 Dijkstra 算法:像水波一样向四面八方均匀扩散，完全不知道终点在哪个方向，扩展的节点最多、最慢。它是支配关系里的下界，任何可采纳启发式都支配它。
- $h = h^\ast$:最强的可采纳启发式。 它给出每个节点到终点的精确真实代价。此时 A* 像开了天眼，沿着最优路径直奔终点，几乎不浪费一次展开（除非有并列最优路径）。它是支配关系里的上界:不可能有可采纳启发式比它更大（再大就高估了）。问题是 $h^\ast$ 本身就需要解一遍最短路才能得到，“为了算 $h$ 先解一遍原问题”显然得不偿失，所以它只是理论标杆，不可直接使用。
于是整个图景串起来了。所有可采纳启发式都被夹在这条链条之间:
\[0 \;=\; h_{\text{Dijkstra}} \;\le\; h \;\le\; h^\ast \;=\; h_{\text{完美}}\]越靠右、越接近 $h^\ast$，搜索越快;越靠左、越接近 $0$，搜索越像盲目的 Dijkstra。这就是那句关键权衡:启发式越接近真实代价，搜索越快;但一旦越过 $h^\ast$（高估），就丢掉了最优性保证。 我们的目标，就是在“不高估”这道红线之下，把 $h$ 顶得尽量高。
回到曼哈顿 vs 欧氏:在四连通网格上，对任意节点都有 $h_{\text{euc}} = \sqrt{dx^2 + dy^2} \le dx + dy = h_{\text{man}}$（这正是三角不等式 / 范数不等式 $\lVert v \rVert_2 \le \lVert v \rVert_1$）。所以曼哈顿支配欧氏，在四连通地图上曼哈顿更快。这就是为什么实践中四连通几乎总用曼哈顿而不是欧氏。
注意一个常见误区:更大不一定可采纳。 支配性的红利只在“$h_2$ 仍然可采纳”时才成立。把启发式硬乘个系数 $h’ = 1.5 \times h_{\text{man}}$ 确实更大、确实更快，但它可能高估，于是落入加权 A（Weighted A）的范畴:速度换最优性，返回的路径不再保证最短，只保证代价不超过最优的 $1.5$ 倍。这是另一套权衡，不要和“可采纳支配”混为一谈。
怎样系统地造出可采纳启发式:松弛问题（relaxed problem）
前面的曼哈顿、欧氏、切比雪夫像是“凭经验拍出来”的。其实它们背后有一个统一、可复制的方法论，这才是本节最该带走的思想:松弛问题（relaxed problem）。
核心思想一句话:去掉原问题的一部分约束，得到一个更容易解的“松弛问题”，松弛问题的最优解代价，就是原问题的一个可采纳启发式。
为什么这套路一定给出可采纳启发式？给一个严格但好懂的论证。原问题的每条合法路径，在松弛问题里仍然是一条合法路径（因为我们只删约束、没加约束，合法集合只会变大不会变小）。所以松弛问题的最优解，是在一个“不小于”原问题可行集的范围里取最小，结果只可能更小或相等:
\[h_{\text{relaxed}}(n) = \text{（松弛问题最优代价）} \;\le\; h^\ast(n) = \text{（原问题最优代价）}\]这恰好就是可采纳的定义 $h \le h^\ast$。所以“松弛 → 求松弛最优 → 当作启发式”是一台自动生产可采纳启发式的机器。 而且额外送你一条:由松弛问题导出的启发式通常自动满足一致性。
用这台机器回看本节的三个距离，它们瞬间变得不再神秘:
- 去掉“障碍物”这条约束 → 在空地图上算最短步数。
- 若动作是四连通单位步，空地图最优解就是 $dx + dy$ → 曼哈顿。
- 若动作是八连通斜直同价，空地图最优解就是 $\max(dx, dy)$ → 切比雪夫。
- 同时去掉“障碍物”和“只能沿格子走”两条约束 → 允许笔直穿越，最短就是直线距离 $\sqrt{dx^2 + dy^2}$ → 欧氏。
看出门道了吗?去掉的约束越多，问题越松，启发式越小（越保守、越接近 $0$）;保留的约束越多，松弛越轻，启发式越大（越接近 $h^\ast$、越快）。 欧氏比曼哈顿小，正是因为它多松了一条“只能走格子”的约束。这给了我们一条设计原则:在“松弛后仍能廉价求解”的前提下，尽量少删约束，这样得到的启发式既可采纳、又尽量贴近真实，效率最高。
这套方法的威力远不止网格寻路。它是经典 AI 搜索里设计启发式的通用范式:
- 八数码 / 十五数码拼图:去掉“一次只能移一个、且只能移到空格”的约束，允许任意拼块直接瞬移到目标位 → 得到“错位拼块数（misplaced tiles）”启发式;只松一半约束（允许穿越其他拼块但仍逐格移动） → 得到更强的“曼哈顿距离之和”启发式，后者支配前者，所以更快。
- 旅行商、规划问题等:都能通过删去某类约束，得到可计算的下界作为启发式。
最后，把多个启发式合并起来更强。 如果你手上有好几个都可采纳的启发式 $h_1, h_2, \dots, h_k$（比如来自不同的松弛方式），取它们的逐点最大值:
\[h(n) = \max\bigl(h_1(n), h_2(n), \dots, h_k(n)\bigr)\]这个 $h$ 仍然可采纳（因为每个 $h_i \le h^\ast$，它们的最大值也 $\le h^\ast$），而且支配其中每一个（按定义它逐点都 $\ge$ 任意 $h_i$）。代价只是多算几次 $h$。这是把多源信息“免费”升级成更强启发式的标准技巧。
本节小结
- 启发式 $h$ 的红线是可采纳（不高估，$h \le h^\ast$）;一致性更强，本节几个标准距离都满足。
- 选距离的第一步是看移动模型:四连通配曼哈顿、八连通斜直同价配切比雪夫、斜步更贵配对角线、通用兜底用欧氏。配错（如斜走却用曼哈顿）会高估并破坏最优性。
- 支配性:都可采纳时，$h$ 越大、越接近 $h^\ast$，展开节点越少、越快;$h = 0$ 退化成 Dijkstra（最慢）、$h = h^\ast$ 直达终点（最快但不可得）。
- 松弛问题是系统导出可采纳启发式的统一方法:删约束 → 解松弛最优 → 当启发式。删得越少、启发式越强;多个可采纳启发式取逐点最大值，可得到更强且仍可采纳的合并启发式。
变体与应用：加权 A\、IDA\、D\* Lite、JPS，以及实战
标准 A（A-star）很强，但它不是万能的。在不同的实际场景里，人们常常面临不同的瓶颈：有时是速度不够快，有时是内存装不下，有时是地图在动态变化，有时是网格太规整、A* 做了太多无用功。针对这些痛点，研究者们设计了一系列 A 的变体（variant）。本节逐一介绍最常见的四个变体，再谈谈它们各自最适合的实战场景。
为了让讲解连贯，先快速回顾一下 A* 的核心评估函数：
\[f(x) = g(x) + h(x)\]其中 $g(x)$ 是从起点到当前节点 $x$ 已经走过的真实代价（cost），$h(x)$ 是从 $x$ 到终点的启发式估计代价（heuristic）。A* 每次从优先队列里取出 $f$ 值最小的节点来扩展（expand）。如果启发函数 $h$ 满足可采纳性（admissibility），即从不高估真实代价（$h(x) \le h^(x)$，这里 $h^$ 是真实的最短剩余距离），那么 A* 保证找到最优解（optimal solution）。下面所有变体，都是围绕这个公式做文章。
一、加权 A（Weighted A）：用最优性换速度
痛点。 在很多应用里，我们其实不需要绝对最优的路径，只需要一条“足够好”的路径，而且要快。标准 A* 因为要保证最优，往往会扩展很多 $f$ 值相近的节点，显得“犹豫不决”。
做法。 加权 A* 只改一个地方：给启发项 $h$ 乘上一个大于 $1$ 的权重 $w$：
\[f(x) = g(x) + w \cdot h(x), \quad w > 1\]直觉。 $w$ 越大，意味着算法越“相信”启发函数指向终点的方向，越倾向于一头扎向终点（贪心），而不去仔细权衡已经走过的代价 $g$。极端情况：
- 当 $w = 1$ 时，就是标准 A*，最优但慢。
- 当 $w \to \infty$ 时，$g$ 项被淹没，退化为贪心最佳优先搜索（greedy best-first search），很快但可能绕远路。
- $w$ 取 $1$ 到无穷之间的值，就是在“快”和“好”之间做权衡（trade-off）。
严谨的保证：有界次优（bounded suboptimality）。 加权 A* 牺牲了最优性，但牺牲得“有节制”。可以证明：如果原始启发 $h$ 是可采纳的，那么加权 A* 找到的路径代价，最多是最优代价的 $w$ 倍。即设算法返回路径代价为 $C$，最优代价为 $C^*$，则
\[C \le w \cdot C^*\]这就是“有界次优”。比如取 $w = 1.5$，你就知道结果最差也只会比最优长 $50\%$，但通常实际差距远小于这个上界，而扩展的节点数却可能减少一大截。这是一笔很划算的买卖，因此加权 A* 在工程上极为常用。
一句话适用场景： 实时性要求高、对路径质量可以容忍小幅次优的场景，比如游戏里大量单位同时寻路、需要在毫秒级给出答案的服务。
二、IDA（迭代加深 A，Iterative Deepening A-star）：用时间换内存
痛点。 A* 要把优先队列（open list）和已访问集合（closed list）都存在内存里。在状态空间巨大的问题中（比如 $15$-puzzle、魔方），这些表会爆掉内存。换句话说，A* 的瓶颈常常不是时间，而是空间。
做法。 IDA* 把 A* 和迭代加深搜索（iterative deepening）结合起来。它不维护庞大的优先队列，而是反复做深度优先搜索（DFS），每一轮设一个 $f$ 值的阈值（threshold）：
- 初始阈值设为起点的 $f$ 值，也就是 $h(\text{start})$。
- 做一次 DFS，凡是 $f(x)$ 超过当前阈值的节点就剪枝（prune），不再往下走，同时记录这些被剪掉节点中最小的 $f$ 值。
- 如果这一轮没找到终点，就把阈值更新为“上一轮被剪掉的最小 $f$ 值”，再重新做一次 DFS。
- 重复，直到找到终点。
直觉。 它像是“画一圈圈等高线”：每一轮只探索 $f$ 值不超过某个阈值的区域，找不到就把圈扩大一点，再来一遍。因为用的是 DFS，任意时刻内存里只需要保存当前这一条搜索路径（栈深度），空间复杂度从 A* 的指数级降到了与解的深度成正比的线性级。
代价。 浅层节点会被反复重新访问（每一轮 DFS 都从头来过），所以时间上有冗余。但在很多问题里，节点数随深度指数增长，最深的一层就占了绝大部分工作量，重复访问浅层的开销相对可以接受。
下面是 IDA* 的伪代码（pseudocode）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function IDA_star(start):
threshold = h(start)
loop:
# 返回值：要么是 FOUND，要么是下一轮的新阈值
result = search(start, g=0, threshold)
if result == FOUND:
return 找到的路径
if result == infinity:
return 无解
threshold = result # 把阈值扩大到下一圈
function search(node, g, threshold):
f = g + h(node)
if f > threshold:
return f # 超阈值，剪枝，返回这个 f 作为候选新阈值
if node 是终点:
return FOUND
min_next = infinity
for each 邻居 next of node:
result = search(next, g + cost(node, next), threshold)
if result == FOUND:
return FOUND
min_next = min(min_next, result) # 收集被剪掉节点中最小的 f
return min_next
一句话适用场景： 状态空间巨大、内存受限、解的深度不算太深的问题，最经典的就是拼图类问题（如 $8$-puzzle、$15$-puzzle）和魔方求解。
三、D* 与 D* Lite：动态环境下的增量重规划（incremental replanning）
痛点。 前面所有算法都假设地图是静态的：规划之前就完全知道哪里有障碍。但真实机器人不是这样。机器人一边走一边用传感器探测，可能突然发现前方有一堵之前不知道的墙，或者环境本身在变化（有人走过、门关上了）。这时如果每次都从头跑一遍 A*，会非常浪费，因为大部分地图其实没变。
做法的核心思想：增量（incremental）。 D*（Dynamic A-star）系列算法的关键洞察是：当地图只有局部发生变化时，没必要重算全部，只需要修复受变化影响的那部分搜索结果。它复用上一次规划的大量信息，只对被改动波及的节点重新计算，因此重规划（replanning）远快于从零开始。
D* 与 D* Lite 的关系。 最早的 D* 由 Stentz 提出，思路强大但实现复杂。后来 Koenig 和 Likhachev 提出了 D* Lite，它基于另一个增量搜索算法 *LPA（Lifelong Planning A-star）*，在功能上与 D 等价，但逻辑更简洁、更容易实现和分析，因此现在实际系统中更常用 D* Lite。
直觉。 可以把它想象成“局部打补丁”：
- 第一次规划，和 A* 类似，得到一条从起点到终点的路径。这里有个细节，D* Lite 通常从终点向起点反向搜索，这样当机器人移动、起点改变时更新更方便。
- 机器人沿路径前进，传感器发现某处代价变了（比如冒出一堵墙）。
- 算法只把“代价发生变化的节点”及其受影响的邻居标记为不一致（inconsistent），放进优先队列，重新计算这一小片区域，迅速得到修正后的路径。
- 大部分没受影响的节点，它们之前算好的距离值直接复用，不重算。
为了高效判断哪些节点需要更新，D* Lite 为每个节点维护两个值：一个是当前估计的代价 $g$，另一个是基于邻居重新算出的“前瞻”代价（一步前瞻值 rhs，right-hand-side value）。当某节点的 $g$ 和 rhs 不相等时，就说明它“不一致”，需要被处理。算法不断从队列里取出最需要修正的不一致节点来更新，直到与起点相关的部分重新一致为止。
一句话适用场景： 机器人导航（robot navigation），尤其是部分可观测、边走边探索、环境会变化的场合，比如火星车、室内自主移动机器人、未知地形探索。著名的火星探测车就用过 D* 系列算法。
四、Jump Point Search（JPS，跳点搜索）：均匀网格上的大幅加速
痛点。 在均匀代价的栅格地图（uniform-cost grid）上跑 A，会遇到一个尴尬的问题：网格里存在大量对称路径（symmetric paths）。比如从一点走到右下方的另一点，先右后下、先下后右、走锯齿……这些路径长度完全一样。A 会傻乎乎地把这些等价路径上的中间节点全都放进优先队列，逐个扩展，做了海量重复又无意义的工作。
做法的核心思想：跳过中间节点。 JPS 的洞察是：在没有障碍物的开阔区域里，一条直线（或对角线）上的中间格子根本不需要逐个加入队列，因为它们“没有选择”，只能继续往前走。JPS 沿着某个方向一路“跳”过去，直到遇到一个真正有意义的点，称为跳点（jump point），才把它放进优先队列。
什么是真正有意义的“跳点”？ 直觉上，只有在某个格子处，因为旁边有障碍物，导致路径被迫拐弯或多出新的可选方向，这个格子才值得作为决策点（这种格子叫有强制邻居（forced neighbor）的点）。终点也算一个特殊跳点。其余的格子都可以“跳过”，因为在它们那里无需做任何决策。
直觉对比。 标准 A* 像一个人走一步看一步、每一格都停下来登记一次；JPS 像一个人在空旷走廊里一口气冲到走廊尽头或拐角处才停下来思考。两者最终找到的路径完全一样、长度一样最优，但 JPS 把优先队列里的节点数量大幅压缩，扩展次数可能减少一两个数量级，因此在大型开阔网格地图上快得惊人。
重要前提（适用条件）。 JPS 依赖于网格的规整性，它要求：
- 地图是均匀代价的栅格（每一步代价相同，对角线代价为 $\sqrt{2}$ 那种规整设置）。
- 障碍物以格子为单位。
它不适用于带权重的不规则图、导航网格（navigation mesh）等非均匀结构。换句话说，JPS 是为“方格地图”量身定制的优化，越是开阔、障碍稀疏的网格，加速效果越明显。值得强调的是，JPS 是无损加速：它不牺牲最优性（这一点和加权 A* 不同），只是利用网格对称性避免了冗余扩展。
一句话适用场景： 基于均匀栅格地图的游戏寻路（game pathfinding），地图大、格子多、障碍相对稀疏的实时策略游戏（RTS）、塔防、像素地图等。
五、把它们放在一起：怎么选？
为了方便记忆，把四个变体的取舍列成一张对照表（其中“最优性”指是否仍能保证最短路径）：
| 变体 | 改了什么 | 主要换来什么 | 还最优吗 | 典型场景 |
|---|---|---|---|---|
| 加权 A（Weighted A） | $f = g + w \cdot h$，$w>1$ | 用最优性换速度 | 否（有界次优，$\le w \cdot C^*$） | 实时性高、可容忍小幅次优 |
| IDA* | 用迭代加深的 DFS 代替优先队列 | 用时间换内存 | 是 | 状态空间巨大、内存受限、拼图/魔方 |
| D* / D* Lite | 局部增量重规划 | 用复用换重算 | 是（相对当前地图） | 动态/未知环境的机器人导航 |
| JPS（Jump Point Search） | 在网格上跳过无决策中间节点 | 用网格对称性换扩展次数 | 是（无损加速） | 均匀栅格地图上的游戏寻路 |
选择的思路可以这样把握：
- 如果你的瓶颈是速度，且能接受略次优的路径，选加权 A*。
- 如果你的瓶颈是内存（状态空间爆炸），选 IDA*。
- 如果你的环境是动态或边走边发现的，选 D* Lite。
- 如果你在规整的方格地图上做寻路，选 JPS（它可以和加权 A* 等思想叠加使用）。
典型应用领域小结：
- 游戏寻路（game pathfinding）： 最常见的 A* 应用。地图通常是栅格或导航网格，强调实时性，因此 JPS（栅格）与加权 A*（容忍次优）都很受欢迎。
- 机器人路径规划（robot motion planning）： 环境部分可观测、会变化，D* / D* Lite 是主力；也常与采样类规划方法（如 RRT*）配合处理高维构型空间。
- 地图导航（map navigation）： 导航软件在道路网络（带权图）上找最短/最快路线，A* 配合好的启发（如地理直线距离）是基础；大规模路网还会叠加预处理类加速技术（如 Contraction Hierarchies），不在本节的基础范围内。
- 拼图类问题（puzzle solving）： $8$/$15$-puzzle、魔方等，状态空间巨大但解不算太深，IDA* 是经典选择，常配合模式数据库（pattern database）作为强启发。
记住一条主线：所有这些变体都没有推翻 A*，而是在 $f = g + h$ 这个框架上，针对“速度、内存、动态性、网格规整性”这四个不同的瓶颈分别做出取舍。 理解了每个变体“牺牲了什么、换来了什么、还保不保最优”，你就能在具体问题面前迅速选对工具。