编码 · 算法
A* 搜索算法详解：原理、代码与复杂度
简短回答
A* 搜索用于求从起点到单个目标节点的最短路径，它把已付出的代价 g(n) 与对剩余代价的估计 h(n) 结合起来，每次总是扩展 f(n) = g(n) + h(n) 最小的节点。只要启发函数从不高估真实的剩余代价，A* 就保证返回最优路径；而好的启发函数能让它探索的节点远少于 Dijkstra 算法。
A* 解决什么问题
Dijkstra 算法会朝各个方向按距离递增的“圈层”扩展节点，哪怕有些方向是背离目标的。当你知道目标在哪里时，这就是白费功夫。A* 加入了启发函数，即对剩余距离的估计，使搜索被拉向目标。它是游戏、机器人和地图中寻路的标准算法。
A* 由 Peter Hart、Nils Nilsson 和 Bertram Raphael 于 1968 年在《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》中提出。
用大白话讲思路
| 符号 | 含义 |
|---|---|
| g(n) | 从起点到 n 的已知最优路径的代价。 |
| h(n) | 从 n 到目标的代价的启发式估计。 |
| f(n) = g(n) + h(n) | 经过 n 的最便宜完整路径的估计代价。开放集合按 f 排序。 |
- 把起点放入优先队列（开放集合），g = 0，f = h(start)。
- 弹出 f 最小的节点。如果它是目标，就还原路径并停止。
- 对每个邻居，计算暂定的 g = g(current) + 边的代价。如果它优于该邻居已知的 g，就记录下来、设置父节点，并以 f = g + h 把该邻居压入队列。
- 如果开放集合变空，说明没有路径。
当所有节点的 h(n) = 0 时，A* 就恰好变成 Dijkstra 算法。若启发函数完美，它会笔直地沿着一条最优路径前进。
如何选择启发函数
如果启发函数从不高估真实的剩余代价，它就是可采纳的。如果对每条边 n → m 都有 h(n) <= cost(n, m) + h(m)，它就是一致的（或称单调的）。一致的启发函数一定是可采纳的，并且每个节点只需扩展一次。
| 移动方式 | 启发函数 | 公式 |
|---|---|---|
| 网格上 4 个方向，代价为 1 | 曼哈顿距离 | abs(dx) + abs(dy) |
| 8 个方向，对角线代价为 1 | 切比雪夫距离 | max(abs(dx), abs(dy)) |
| 8 个方向，对角线代价为 √2 | 八方向距离（octile） | max(dx, dy) + (sqrt(2) - 1) * min(dx, dy)，其中 dx、dy 取绝对值 |
| 任意方向，直线移动 | 欧几里得距离 | sqrt(dx * dx + dy * dy) |
网格上的 Python 实现
下面的网格有 5 行 7 列；# 表示第 5 列的墙。格子用 (row, column) 表示。可以上下左右移动，代价为 1，所以曼哈顿距离是可采纳且一致的。
import heapq
def a_star(grid, start, goal):
rows, cols = len(grid), len(grid[0])
h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
g = {start: 0}
parent = {start: None}
open_heap = [(h(start), start)]
while open_heap:
f, cur = heapq.heappop(open_heap)
if cur == goal:
path = []
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
if f > g[cur] + h(cur):
continue # outdated entry
r, c = cur
for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != "#":
ng = g[cur] + 1
if ng < g.get(nb, float("inf")):
g[nb] = ng
parent[nb] = cur
heapq.heappush(open_heap, (ng + h(nb), nb))
return None
grid = [".......",
".....#.",
".....#.",
".....#.",
"......."]
path = a_star(grid, (2, 3), (2, 6))
print(len(path) - 1, path)
# 7 [(2, 3), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]逐步演示一个例子
在上面的网格中，起点 (2, 3) 沿直线到目标 (2, 6) 有 3 步，所以第一个 f 为 0 + 3 = 3。墙挡住了这条直线，真正的最短路径有 7 步。A* 分阶段发现这一点：先扩展所有 f 最小的格子，用完之后再扩展次小的 f。
| f 值 | 扩展的格子（按顺序） | 发生了什么 |
|---|---|---|
| 3 | (2, 3), (2, 4) | 径直朝目标前进，直到遇墙。 |
| 5 | (1, 3), (1, 4), (2, 2), (3, 3), (3, 4) | 向旁边或后退一步要多付 2；仍然被挡住。 |
| 7 | (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 6), (2, 1), (2, 6) | 绕过墙的上方；目标在 f = 7 时被弹出。 |
A* 在 32 个开放格子中扩展了 15 个。Dijkstra 算法（即 h = 0 的 A*）会扩展全部 32 个，因为每个开放格子离起点都不超过 7 步。在大型开阔地图上，节省的更多。
时间与空间复杂度
| 指标 | 开销 | 原因 |
|---|---|---|
| 最坏时间 | O((V + E) log V) | 与 Dijkstra 相同：h = 0 这样无用的启发函数起不到任何引导作用。 |
| 典型时间 | 远少于 Dijkstra | 完全取决于启发函数的质量；完美的 h 只会扩展路径上的节点。 |
| 空间 | O(V) | 开放堆、g 值和父节点。在超大地图上，内存往往才是真正的限制。 |
节省内存的变体包括 IDA*（迭代加深 A*），它只保存当前路径，代价是要重复访问节点。
何时使用 A* 及实际应用
- 当只有一个目标，且有廉价而可采纳的剩余代价估计时（例如地图上的几何距离），使用 A*。
- 需要到许多节点或所有节点的距离，或找不到有用的启发函数时，使用 Dijkstra。无权图上启发函数帮助不大时，使用 BFS。
- 电子游戏：瓦片地图和导航网格上的单位移动。
- 机器人与路线规划，常与预先计算的地标或层次结构结合使用。
- 解谜：以方块的曼哈顿距离为启发函数的 8 数码和 15 数码问题。
常见问题
A* 一定是最优的吗？
当启发函数可采纳，即从不高估剩余代价时，A* 返回最优路径。如果启发函数高估，可能返回更长的路径。
A* 和 Dijkstra 算法有什么区别？
Dijkstra 按已付出的代价 g(n) 给节点排序。A* 按 g(n) + h(n) 排序，其中 h 估计到目标的剩余代价。h = 0 的 A* 就是 Dijkstra。
在网格上应该用哪种启发函数？
4 方向移动用曼哈顿距离；8 方向移动则根据对角线代价选择切比雪夫距离或八方向距离；自由移动用欧几里得距离。
什么是贪心最佳优先搜索？
它只按 h(n) 给节点排序，忽略已付出的代价。通常很快，但不保证得到最短路径。