假设地图中存在起点和终点,路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划,或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法,和 Dijkstra 算法相比,A* 采用启发式的搜索策略,能够更快地搜索出最短路径。
1.前言
给定一个包含起点 (白色圆点) 和终点 (黑色圆点) 的图,有很多条路径可以从起点到达终点,但是很多不是最短路径。如上图所示,黑色虚线为最短路径,红色虚线不是。
Dijkstra 算法是其中一种求解起点到终点最短路径的算法,在用于无权重图时,Dijkstra 算法就是宽度优先 (BFS) 的方法。A* 对 Dijkstra 进行了优化,引入启发式的搜索策略,可以更快地搜索出最短路径。
2.Dijkstra算法
假设起点是 s,终点是 e,Dijkstra 算法的主要包括下面的流程。
- 步骤一:用一个集合 F 保存已经访问过的节点,初始时 F 只包含起点 s。用一个数组 D 保存起点 s