知足常乐|A* 路径搜索算法假设地图中存在起点和终点

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

步骤一：用一个集合 F 保存已经访问过的节点，初始时 F 只包含起点 s 。用一个数组 D 保存起点 s 到其余所有节点的最短路径。在开始时， D 的数值用下面的公式计算。

初始距离数组 D

步骤二：找到一个不在 F 中，并且 D[u] 最小的节点 u 。 D[u] 就是起点 s 到节点 u 的最短距离，把 u 加入 F 。
步骤三：用节点 u 更新数组 D 中的最短距离，如下面的公式。

更新距离数组 D

步骤四：如果 F 中已经包含终点 e ，则最短路径已找到，否则继续执行步骤二。

Dijkstra 算法可以用于有权重 (即节点之间的距离是不同的) 和无权重 (节点间距离一样) 的图，如果用于无权重的图， Dijkstra 算法就是 BFS 算法。
下图展示了用 Dijkstra 算法搜索无权重图最短路径的过程，橙色表示算法搜索过的区域，颜色由浅到深，表示搜索的深度 (先后顺序) 。浅橙色表示最先搜索到的节点，而深橙色表示最后搜索到的节点。

Dijkstra 算法搜索过程
3.A* 算法A* 算法加入了启发式的搜索策略，在搜索时间上通常优于 Dijkstra 算法。 A* 使用了一个估计值 F 代表某一个节点到终点的估计距离，计算公式如下：

A* 算法估计值 F 计算公式
另外 A* 包含两个列表， open list 和 close list ， open list 保存了等待探索的节点，而 close list 表示已经探索过的节点。
A* 算法的流程如下：

步骤一：把起点 s 放入到 open list 里面。
步骤二：检查 open list ，如果终点 e 在 open list 里面，则路径搜索完成。如果 open list 为空，则说明不存在路径。
步骤三：在 open list 里面选择估计值 F 最小的节点 u ，作为当前节点，然后加入 close list 里面。
步骤四：取得所有节点 u 可以直接到达的节点 v ，然后更新 open list 。更新规则：如果 v 在 close list 里，则不处理；如果 v 不在 open list 里面，则把 v 加入 open list ，其对应 F 值为 G(u)+distance(u,v)+H(v)；如果 v 在 open list 里面，则检查 v 是否有更小的 F 值 (如果有更小 F 值，就更新 v 的 F 值)；