假设地图中存在起点和终点,路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划,或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法,和 Dijkstra 算法相比,A* 采用启发式的搜索策略,能够更快地搜索出最短路径。
图中的起点和终点
给定一个包含起点 (白色圆点) 和终点 (黑色圆点) 的图,有很多条路径可以从起点到达终点,但是很多不是最短路径。如上图所示,黑色虚线为最短路径,红色虚线不是。
Dijkstra 算法是其中一种求解起点到终点最短路径的算法,在用于无权重图时,Dijkstra 算法就是宽度优先 (BFS) 的方法。A* 对 Dijkstra 进行了优化,引入启发式的搜索策略,可以更快地搜索出最短路径。
假设起点是 s,终点是 e,Dijkstra 算法的主要包括下面的流程。
初始距离数组 D
更新距离数组 D
Dijkstra 算法可以用于有权重 (即节点之间的距离是不同的) 和无权重 (节点间距离一样) 的图,如果用于无权重的图,Dijkstra 算法就是 BFS 算法。
下图展示了用 Dijkstra 算法搜索无权重图最短路径的过程,橙色表示算法搜索过的区域,颜色由浅到深,表示搜索的深度 (先后顺序)。浅橙色表示最先搜索到的节点,而深橙色表示最后搜索到的节点。
Dijkstra 算法搜索过程
A* 算法加入了启发式的搜索策略,在搜索时间上通常优于 Dijkstra 算法。A* 使用了一个估计值 F 代表某一个节点到终点的估计距离,计算公式如下:
A* 算法估计值 F 计算公式
另外 A* 包含两个列表,open list 和 close list,open list 保存了等待探索的节点,而 close list 表示已经探索过的节点。
A* 算法的流程如下:
下面是 A* 搜索最短路径的示例,每一个节点中左边的数字表示 G(n) 即真实距离,右边的数字表示 H(n) 即启发函数计算的距离。F 值就是 G(n)+H(n),在下面的例子中 H(n) 用曼哈顿距离计算 (在下面的例子中等于没有障碍物时,n 到终点 e 的最短距离)。
A* 算法的例子
如果不设置启发函数,则 A* 就是 Dijkstra 算法,这时可以找到最短路径。
如果启发函数 H(n) 的值一定小于等于 n 到终点的实际距离,则 A* 可以保证找到最短路径。
如果 H(n) 的值等于 n 到终点的实际距离,则 A* 会直接找到最短路径,而不用扩展搜索额外的节点,此时运行是最快的。
如果 H(n) 的值有可能大于 n 到终点的实际距离,则 A* 算法不一定可以找到最短路径,但是运行速度会比较快。
Amit’s A* Pages 地址: http://theory.stanford.edu/~amitp/GameProgramming/