4. A*算法详解：从原理到实战
大家好，我是你们的老朋友。今天我们来聊聊路径规划里最经典、也最实用的算法——A*。说实话，我在做机器人导航的这些年里，A* 几乎是我每天都要打交道的算法。它不像 Dijkstra 那样盲目，也不像贪心算法那样容易掉坑。A* 找到了一个很好的平衡点。
嗯，咱们直接进入正题。
4.1 A*算法核心原理
A* 本质上是一种启发式搜索算法。它怎么工作的？说白了，就是每次从待选节点里，挑一个「看起来最有希望」的节点去扩展。
这个「看起来最有希望」怎么量化？A* 用了一个评价函数：
f(n) = g(n) + h(n)- g(n)：从起点到当前节点 n 的实际代价。这个值是已知的。
- h(n)：从当前节点 n 到终点的估计代价。这个值是猜的，但猜得越准，算法跑得越快。
- f(n)：总估计代价。A* 每次选 f(n) 最小的节点来扩展。
我刚开始学的时候，总觉得这个公式太简单了。但后来在项目中才发现，真正的难点不在公式，而在 h(n) 的设计。
核心要点：A* 保证找到最短路径的充要条件是——启发函数 h(n) 必须满足「可采纳性」，即 h(n) ≤ 实际代价。说白了，你不能过度乐观。
4.2 启发函数设计——经验之谈
启发函数是 A* 的灵魂。我见过太多人把 A* 跑得比 Dijkstra 还慢，就是因为 h(n) 设计得太差。这里我分享几种常用的启发函数，以及我踩过的坑。
4.2.1 曼哈顿距离
适用于只允许上下左右移动的栅格地图。公式很简单：
h(n) = |x1 - x2| + |y1 - y2|我在一个仓储机器人项目里用过这个。当时地图是标准的仓库过道，机器人只能走正交方向。曼哈顿距离跑起来非常快，而且保证最优。
4.2.2 欧几里得距离
适用于允许任意方向移动的场景：
h(n) = sqrt((x1 - x2)² + (y1 - y2)²)但要注意！欧几里得距离在栅格地图上往往低估实际代价。因为机器人走斜线时，实际步长是 1.414，但欧几里得距离算出来可能更小。这会导致 A* 扩展更多节点，效率下降。
我曾经踩过的坑：在一个户外机器人项目中，我用了欧几里得距离，结果 A* 跑了 3 秒才出结果。换成对角线距离后，0.5 秒就搞定了。差别就这么大。
4.2.3 对角线距离
这是栅格地图上我最推荐的一种：
dx = |x1 - x2|
dy = |y1 - y2|
h(n) = (dx + dy) + (√2 - 2) * min(dx, dy)它既考虑了正交移动，也考虑了斜向移动。说白了，就是曼哈顿距离的升级版。
| 启发函数 | 适用场景 | 效率 | 最优性 |
|---|---|---|---|
| 曼哈顿距离 | 仅正交移动 | 高 | 保证 |
| 欧几里得距离 | 任意方向 | 中 | 保证 |
| 对角线距离 | 正交+斜向 | 高 | 保证 |
4.3 在栅格地图上的实现
好了，理论说完了，咱们看看怎么在栅格地图上实现 A*。栅格地图说白了就是一个二维数组，0 表示可通行，1 表示障碍物。
我习惯用两个列表来管理节点：
- Open List：待考察的节点。每次从中选 f(n) 最小的。
- Closed List：已经考察过的节点。不再处理。
伪代码流程是这样的：
1. 把起点加入 Open List
2. 循环直到 Open List 为空：
a. 从 Open List 中取出 f(n) 最小的节点，记为 current
b. 如果 current 是终点，路径找到，结束
c. 把 current 从 Open List 移除，加入 Closed List
d. 遍历 current 的所有邻居：
- 如果邻居不可通行或在 Closed List 中，跳过
- 计算 g、h、f 值
- 如果邻居不在 Open List 中，加入
- 如果在 Open List 中但新 g 值更小，更新
3. 如果 Open List 为空，无路可走你想想看，这个流程其实很直观。但有一个细节很多人会忽略——邻居的遍历顺序。我建议先检查正交方向（上下左右），再检查斜向方向。这样在大多数情况下能更快找到路径。
4.4 代码实战——Python 实现
下面是我写的一个精简版 A* 实现。这个版本我用了很多次，稍微改改就能用到实际项目中。
import heapq
import math
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.g = 0
self.h = 0
self.f = 0
self.parent = None
def __lt__(self, other):
return self.f < other.f
def heuristic(a, b):
# 对角线距离
dx = abs(a.x - b.x)
dy = abs(a.y - b.y)
return (dx + dy) + (math.sqrt(2) - 2) * min(dx, dy)
def a_star(grid, start, end):
rows, cols = len(grid), len(grid[0])
open_list = []
closed_set = set()
start_node = Node(start[0], start[1])
end_node = Node(end[0], end[1])
heapq.heappush(open_list, start_node)
# 8个方向：上下左右 + 4个斜角
directions = [(-1,0),(1,0),(0,-1),(0,1),
(-1,-1),(-1,1),(1,-1),(1,1)]
while open_list:
current = heapq.heappop(open_list)
if (current.x, current.y) == (end_node.x, end_node.y):
# 回溯路径
path = []
while current:
path.append((current.x, current.y))
current = current.parent
return path[::-1]
closed_set.add((current.x, current.y))
for dx, dy in directions:
nx, ny = current.x + dx, current.y + dy
# 边界检查
if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
continue
# 障碍物检查
if grid[nx][ny] == 1:
continue
# 已访问检查
if (nx, ny) in closed_set:
continue
neighbor = Node(nx, ny)
# 斜向移动代价为1.414，正交为1
move_cost = math.sqrt(2) if dx != 0 and dy != 0 else 1
neighbor.g = current.g + move_cost
neighbor.h = heuristic(neighbor, end_node)
neighbor.f = neighbor.g + neighbor.h
neighbor.parent = current
# 检查是否已在open_list中且g值更小
in_open = False
for i, node in enumerate(open_list):
if (node.x, node.y) == (nx, ny) and node.g <= neighbor.g:
in_open = True
break
if not in_open:
heapq.heappush(open_list, neighbor)
return None # 无路径我的小建议：实际项目中，别用列表遍历来检查 open_list 中是否有重复节点。用字典维护一个「节点位置→g值」的映射，能大幅提升性能。尤其是地图大的时候，这个优化能省下好几秒。
4.5 知识体系总览
下面这张图是我自己整理的 A* 算法知识体系。你可以把它当作一个快速索引，遇到问题回来翻翻。
4.6 避坑指南
最后，我分享几个实战中容易踩的坑：
- 启发函数不可采纳：如果你用了不可采纳的 h(n)，A* 可能找不到最短路径。我曾经在一个项目中用了过估计的启发函数，结果机器人绕了远路，被客户投诉了。
- Open List 实现不当：用普通列表 + 遍历找最小值，复杂度是 O(n)。地图一大就卡死。一定要用优先队列（heapq）。
- 忽略斜向移动代价：正交移动代价是 1，斜向是 √2 ≈ 1.414。如果都按 1 算，路径会失真。
- 地图太大怎么办？：A* 在超大栅格地图上会变慢。这时候可以考虑分层 A*（Hierarchical A*）或者跳点搜索（JPS）。嗯，这个我们后面有机会再聊。
好了，A* 算法就讲到这里。代码我已经贴出来了，你直接复制到 Python 环境里就能跑。试试看，换几个不同的启发函数，看看路径和效率有什么变化。实践出真知嘛。