A* 路径规划 — 算法说明文档
← 返回模拟器
|
← 返回首页
1. 概述
A*（A-Star） 是人工智能和游戏开发中最经典的启发式路径搜索算法，由 Peter Hart、Nils Nilsson 和 Bertram Raphael 于 1968 年在斯坦福研究院（SRI）提出。
它巧妙地融合了两种策略：
- Dijkstra 算法的完备性 —— 保证找到最短路径
- 贪心最佳优先搜索的效率 —— 利用启发式函数引导搜索方向
A* 既不会像 Dijkstra 那样无差别地向所有方向扩展，也不会像贪心搜索那样可能走入死胡同。只要启发式函数满足可容许性（admissible），A* 就一定返回最优路径，并且扩展的节点数不超过任何其他最优算法。
2. 核心公式
\[
\boxed{
f(n) = g(n) + h(n)
}
\]
其中每个节点的评估值 \(f(n)\) 由两部分组成：
| 符号 | 名称 | 含义 |
|---|
| \(g(n)\) |
实际代价（cost-so-far） |
从 起点 到当前节点 \(n\) 的已知实际代价 |
| \(h(n)\) |
启发式估计（heuristic） |
从当前节点 \(n\) 到 终点 的估计剩余代价 |
| \(f(n)\) |
总估计代价 |
经过节点 \(n\) 的完整路径的估计总代价 |
直觉理解：
- \(g(n)\) 告诉你"我已经走了多远"——已付出的代价
- \(h(n)\) 告诉你"大概还要走多远"——对未来的乐观估计
- \(f(n)\) 是"经过这条路的总代价估计"——A* 总是优先扩展 \(f\) 值最小的节点
3. 启发式函数
启发式函数 \(h(n)\) 是 A* 的灵魂。选择不同的 \(h(n)\) 会显著改变算法行为。
3.1 三种常见启发式
设当前节点为 \((r_1, c_1)\)，终点为 \((r_2, c_2)\)，令 \(\Delta r = |r_1 - r_2|,\ \Delta c = |c_1 - c_2|\)：
曼哈顿距离
\[
h(n) = \Delta r + \Delta c
\]
只允许上下左右移动时的最优启发式。网格上最常见的默认选择。
欧几里得距离
\[
h(n) = \sqrt{\Delta r^2 + \Delta c^2}
\]
允许任意方向移动时的直线距离。较曼哈顿更激进，扩展节点更少。
切比雪夫距离
\[
h(n) = \max(\Delta r, \Delta c)
\]
允许8方向移动（含对角线）时的最优启发式。国王在棋盘上移动的距离。
3.2 启发式权重
引入权重参数 \(w\) 可以调节算法行为：
\[
f(n) = g(n) + w \cdot h(n)
\]
| \(w\) | 行为 | 说明 |
|---|
| \(w = 0\) | 退化为 Dijkstra | 忽略启发式，保证最短路径但扩展大量节点 |
| \(w = 1\) | 标准 A* | 最优效率，保证最短路径 |
| \(w > 1\) | 加权 A*（Weighted A*） | 更贪心，搜索更快但路径可能不是最短 |
3.3 可容许性与一致性
- 可容许性：\(h(n) \leq h^*(n)\)，即启发式永远不高估剩余代价。满足此条件则 A* 保证最优解。
- 一致性（单调性）：\(h(n) \leq c(n, n') + h(n')\)，即三角不等式成立。一致性是可容许性的充分条件，且保证每个节点只被扩展一次。
在网格地图上，曼哈顿距离和切比雪夫距离都满足一致性（在各自允许的移动规则下），因此 A* 在此场景下行为优良。
4. 算法流程
A* 的搜索过程可以概括为以下步骤：
- 初始化：将起点加入开放列表（openSet），记录起点的 \(g=0\) 和 \(f = h(\text{start})\)
- 选择节点：从 openSet 中取出 \(f\) 值最小的节点作为当前节点
- 检查目标：如果当前节点就是终点，则通过反向指针重建路径并返回
- 扩展邻居：对当前节点的每个邻居，计算 tentative \(g\) 值；如果比之前记录的更小，则更新该邻居的 \(g\)、\(f\) 和父节点指针，并将其加入 openSet
- 标记已探索：将当前节点移入 closedSet
- 循环：重复步骤 2-5，直到 openSet 为空（无路径可达）或找到终点
整个搜索过程在模拟器中通过颜色编码完全可视化——青色为 openSet，琥珀色为 closedSet，黄色为当前正在处理的节点。
5. 与其他算法的对比
| 算法 | 评估函数 | 最优性 | 扩展范围 | 适用场景 |
|---|
| BFS |
无（按层扩展） |
仅无权图 |
中等 |
均匀代价网格 |
| Dijkstra |
\(f = g\) |
最优 |
大（均匀扩散） |
任意代价图 |
| 贪心最佳优先 |
\(f = h\) |
不保证 |
小 |
快速近似解 |
| A* |
\(f = g + h\) |
最优（h 可容许） |
中等（有引导） |
兼顾速度与最优性 |
A* 在 Dijkstra 和贪心搜索之间取得了精妙的平衡：
- 如果 \(h(n) = 0\)，A* 退化为 Dijkstra
- 如果 \(h(n) \gg g(n)\)，A* 趋近于贪心搜索
- 在两者之间，A* 在朝向目标的方向上做优先探索
6. 数据结构与复杂度
6.1 优先队列
A* 的性能瓶颈在于反复从 openSet 中取出最小 \(f\) 值节点。最优实现使用二叉堆（Binary Heap）：
| 操作 | 数组（朴素） | 二叉堆 |
|---|
| 插入 | \(O(1)\) | \(O(\log N)\) |
| 取最小值 | \(O(N)\) | \(O(\log N)\) |
| 更新键值 | \(O(1)\) | \(O(\log N)\) |
本模拟器为了代码清晰，使用数组排序实现，适合教学演示。实际工程中应使用二叉堆或斐波那契堆。
6.2 时间复杂度
\[
O(b^d)
\]
其中 \(b\) 是分支因子（网格上为 4 或 8），\(d\) 是解的深度。由于启发式的剪枝效果，实际复杂度远低于最坏情况。启发式越准确，搜索越高效。
7. 使用指南
7.1 基本操作
| 功能 | 操作 | 说明 |
|---|
| 设置起点 | 点击格子设为起点 | 绿色格子，表示搜索起点 |
| 设置终点 | 点击格子设为终点 | 红色格子，表示搜索目标 |
| 绘制障碍物 | 在空白格子上拖动 | 灰色斜线纹理，表示不可通行区域 |
| 清除障碍物 | 在障碍格子上拖动 | 移除此处的障碍 |
| 开始搜索 | 点击"开始"按钮 | 执行完整的 A* 搜索过程 |
7.2 学习工具
- 逐步执行：按 → 键或"单步"按钮，每次扩展一个节点，观察 A* 如何选择下一个最优节点
- 回退：按 ← 键回退到上一步，反复对比每一步的决策逻辑
- 自动播放：5 档速度可调，从极慢（可看清每一步）到极快
- 快进：一键跑完整个搜索，直接查看最终路径
- 悬停查看：鼠标悬停在已探索格子上，显示该节点的 \(g\)、\(h\)、\(f\) 具体数值
7.3 实验探索
- 调整启发式权重 \(w\)：调节滑块，对比 Dijkstra（\(w=0\)）、标准 A*（\(w=1\)）和加权 A*（\(w>1\)）的搜索范围差异
- 切换启发式函数：在曼哈顿/欧几里得/切比雪夫之间切换，观察搜索范围如何变化
- 复杂迷宫：绘制复杂障碍布局，测试 A* 在复杂环境中的路径规划能力
- 无解验证：用障碍完全包围终点，观察 A* 如何遍历所有可达节点后正确报告失败
8. 模拟器交互与可视化
8.1 邻居扩展
支持 8 方向移动（包括对角线），对角线移动代价为 \(\sqrt{2} \approx 1.414\)，正交移动代价为 \(1\)。对角线移动时检查两侧障碍防止"穿墙"。
8.2 状态可视化
| 颜色 | 状态 | 含义 |
|---|
| 绿色 | 起点 |
| 红色 | 终点 |
| 灰色 | 障碍物（带斜线纹理） |
| 青色 | Open Set — 待探索的候选节点，\(f\) 值标注在格子上 |
| 琥珀 | Closed Set — 已探索过的节点 |
| 黄色 | 当前正在处理的节点 |
| 绿色路径 | 找到的最优路径 |
9. 教学价值
通过这个模拟器，学生可以直观理解：
- \(f = g + h\) 的含义：看颜色分布理解 A* 如何在"已付代价"和"未来估计"之间平衡
- 启发式函数的影响：切换曼哈顿/欧几里得/切比雪夫，观察搜索范围的变化
- 权重的作用：\(w=0\) 时 A* 变成 Dijkstra 的"同心圆扩散"；\(w>1\) 时变成朝向目标的窄带搜索
- 最优性：可视化验证——找到的路径确实是最短的
- 完备性：当没有路径可达时，A* 会耗尽 openSet 后正确报告失败
- 对角移动的特殊处理：观察障碍物边角处的切割问题
10. 参考资料
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics.
- Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach (4th ed.), Chapter 3.
- Amit Patel's Introduction to the A* Algorithm (Red Blob Games) — 经典在线教程。