2. A星算法基础
A星（A*）算法是路径规划与图搜索领域最经典的启发式搜索算法之一。它通过结合实际代价与估计代价，在保证找到最优路径的同时，大幅减少搜索空间。本节将深入剖析其核心原理、估价函数构成以及两种最常用的距离度量方式。
2.1 启发式搜索原理
与盲目搜索（如广度优先、深度优先）不同，启发式搜索利用启发信息来指导搜索方向。A*算法的核心思想是：每次从开放列表中选择总代价最小的节点进行扩展，从而优先探索“最有希望”的路径。
关键特性： A*算法在满足可采纳性（h(n) ≤ 实际代价）和一致性（单调性）的条件下，保证找到最短路径。
搜索过程维护两个核心列表：
- 开放列表（Open List）： 存放待探索的节点，按 f(n) 值排序。
- 关闭列表（Closed List）： 存放已探索过的节点，避免重复扩展。
2.2 估价函数 f(n) = g(n) + h(n) 详解
估价函数是A*算法的灵魂，它决定了搜索的效率与正确性。其数学表达式为：
f(n) = g(n) + h(n)各分量含义如下表所示：
| 符号 | 名称 | 含义 | 计算方式 |
|---|---|---|---|
| f(n) | 总估价代价 | 从起点经过节点 n 到终点的估计总代价 | g(n) + h(n) |
| g(n) | 实际代价 | 从起点到节点 n 的已知最短路径代价 | 父节点 g 值 + 父节点到 n 的移动代价 |
| h(n) | 启发式代价 | 从节点 n 到终点的估计最小代价 | 由启发函数计算（如曼哈顿距离） |
理解要点： g(n) 保证路径的准确性，h(n) 提供方向性。当 h(n) = 0 时，A*退化为 Dijkstra 算法；当 h(n) 远大于 g(n) 时，算法接近贪心最佳优先搜索。
2.3 曼哈顿距离与欧几里得距离
在网格地图中，h(n) 的选取直接影响搜索效率。最常用的两种启发式距离是曼哈顿距离和欧几里得距离。
2.3.1 曼哈顿距离（Manhattan Distance）
适用于四方向移动（上下左右）的网格。计算两点在标准坐标系上的轴距之和：
h_manhattan(n) = |x_n - x_goal| + |y_n - y_goal|特点：
- 计算简单，仅需整数加减法。
- 在允许四方向移动的网格中，是可采纳且一致的启发式。
- 搜索效率较高，扩展节点数较少。
2.3.2 欧几里得距离（Euclidean Distance）
适用于任意方向移动（八方向或连续空间）。计算两点之间的直线距离：
h_euclidean(n) = sqrt((x_n - x_goal)² + (y_n - y_goal)²)特点：
- 计算开销较大（涉及平方根运算）。
- 在网格地图中，由于移动受限，h(n) 往往低估实际代价，导致扩展节点增多。
- 在连续空间或八方向移动中表现更优。
2.3.3 对比总结
| 对比维度 | 曼哈顿距离 | 欧几里得距离 |
|---|---|---|
| 适用场景 | 四方向网格 | 八方向 / 连续空间 |
| 计算复杂度 | O(1)，仅加减法 | O(1)，含平方根运算 |
| 可采纳性 | 四方向下可采纳 | 八方向下可采纳 |
| 搜索效率 | 高，扩展节点少 | 低，扩展节点较多 |
| 路径质量 | 折线路径 | 更接近直线 |
实践注意： 在网格地图中，如果使用欧几里得距离作为启发式，由于实际移动只能沿网格方向，h(n) 会严重低估代价，导致搜索效率下降。此时可考虑使用切比雪夫距离或对角距离作为替代。
2.4 启发式函数选择指南
在实际工程中，选择合适的启发式函数需要权衡搜索效率与路径最优性：
- 精确匹配移动模型： 四方向网格用曼哈顿距离，八方向网格用切比雪夫距离或对角距离，连续空间用欧几里得距离。
- 权重调整： 若对实时性要求高，可引入权重因子 w，使用 f(n) = g(n) + w * h(n)（w > 1），牺牲最优性换取速度。
- 动态环境： 在动态障碍物场景中，可结合 JPS（Jump Point Search）或 D* Lite 等变体。
工程建议： 在物流路径优化中，若地图为仓库网格（四方向移动），优先使用曼哈顿距离；若为园区道路（八方向移动），使用对角距离；若为开放场地（AGV 任意方向），使用欧几里得距离并配合预处理加速。