A* 搜索
有方向感的 Dijkstra。它在每个位置的代价上加上剩余代价的估计,所以先尝试看起来离终点最近的位置。
- 时间 O((V + E) log V)
- 内存 O(V)
- 使用优先队列
这些是什么意思？
- 代价:一步要付出的成本。迷宫中踩上地面为 1、泥地为 3、水为 9;图中是边上的数字。
- 优先队列:不是先到先出,而是最便宜的先出。
- 估计(h):对剩余代价的猜测。只有它从不偏高,A* 才能保持精确。
- 松弛一条边:检查经过当前位置能否让邻居的代价更低,如果能就采用。
0 / 205 步
- 在队列中
- 当前
- 已完成
- 最便宜的路
- 地面 · 1
- 泥地 · 3
- 水 · 9
- 墙
新: 从 A1 出发,代价 0,到终点估计 26。它是队列中唯一的元素。
空格键：播放或暂停。左右方向键：单步移动。Home 和 End 键：跳转。
试试看： 选择“开阔地”,在 Dijkstra 和 A* 之间切换:两者找到的路代价相同,但 A* 从队列中取出的格子少得多。
工作原理
A* 的工作方式和 Dijkstra 一样,但按 f = 已花代价 + h 来排列队列,其中 h 估计剩余代价。在迷宫里,h 是忽略墙和泥地后到 M 的步数;在图里,是直线距离除以 10。只要 h 从不高估,A* 取出终点时的路就是最便宜的,和 Dijkstra 完全一样。估计越准,需要查看的位置越少。
适用场合
当你只找一个终点并且能估计它有多远时使用 A*:游戏寻路、机器人、地图路线规划。h = 0 时它就是 Dijkstra。可能高估的估计会让 A* 更快,但可能错过最便宜的路。