A* 算法

按「已走代价 + 到终点的估计代价」挑下一步的最短路径搜索算法。

A* 是在图或栅格地图上找最短路径的搜索算法，1968 年由斯坦福研究院的 Hart、Nilsson、Raphael 为 Shakey 移动机器人项目提出。它每次扩展 f(n)=g(n)+h(n) 最小的节点：g(n) 是从起点走到节点 n 已花的实际代价，h(n) 是从 n 到终点的估计代价（启发函数，如直线距离）。只要 h 从不高估真实代价（称为可采纳），A* 保证找到最短路；h 恒为 0 时退化成 Dijkstra 算法，会向四面八方均匀搜索。它常用于移动机器人全局路径规划和游戏寻路；机械臂的高维关节空间一般改用 RRT 等基于采样的规划。考虑车辆转弯约束的变体叫混合 A*。

例子扫地机器人在 5 厘米一格的占据栅格地图上从客厅去卧室：每走一格代价为 1，h 取当前格到卧室的直线距离，A* 绕开被占据的格子得到最短路线，再交给局部规划器去跟踪。

也叫

A星算法、A-star、A* 搜索

相关

Dijkstra 算法、混合 A*、路径规划、代价地图、全局规划与局部规划、快速扩展随机树

来源

Wikipedia: A* search algorithm