A*（A-Star）算法和 Dijkstra 算法一样，都是求最短路径的搜索算法。不过 Dijkstra 算法比较直接，上来就是 BFS 搜索，A* 算法则用了一点“启发”技术。所谓启发，其实都是很简单的距离向量的判断。但是不要小看这一点“启发”，它使得 A* 算法在搜索效率上优于 Dijkstra 算法。

一、A* 算法原理

Dijkstra 算法，它在选择下一个最短路径点的时候，只考虑当前点与起点的距离关系，选择与起点最近的点作为下一个最短路径点。这种策略的思想就是，如果选择的每个点都是与起点最近的点，当选到终点的时候，终点自然也是与起点最近的点，那么这条路径就是最短路径。但是 Dijkstra 算法没有考虑当前点与终点的关系，这就是A*算法的改进处

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

A* 算法的启发函数采用的计算公式是：F(n) = G(h) + H(n)。F(n) 就是 A* 算法对每个点的评估函数，它包含两部分信息：

  • G(n) 是从起点到当前节点 n 的实际代价，也就是从起点到当前节点的移动距离，相邻两个点的移动距离是 1，当前点距离起点越远，这个值就越大；
  • H(n) 是从当前节点 n 到终点的距离评估值，这是一个从当前节点到终点的移动距离的估计值。

A* 算法的搜索过程需要两个表，一个是 Open 表，存放当前已经被发现，但是还没有搜索过的节点；另一个是 Close 表，存放已经搜索过的节点。A* 算法将通过以下步骤搜索最短路径。

（1）初始化 Open 表和 Close 表，将起点加入到 Open 表中。

（2）从 Open 表中取出当前 F(n) 值最小的节点作为当前搜索节点 U，将 U 节点加入到 Close 表中。

（3）对于每一个与 U 可连通的节点（障碍物不相通）V，考察 V：

  • 如果 V 已经在 Close 表中，则对该节点不做任何处理；
  • 如果 V 不在 Open 表中，则计算 F(V)，将 V 的前驱节点设置为 U 并将 V 加入到 Open 表中；
  • 如果 V 在 Open 表中，比较 G(U) + 1 与 G(V) 的大小（H(V) 的值是不变的），如果 G(U) + 1 < G(V)，则令 G(V) = G(U) + 1，同时将 V 的前驱节点设置为 U。

重复步骤（2）和（3），直到第（2）步得到的搜索节点 U 就是终点为止，此时算法结束。

二、距离评估函数

1、曼哈顿距离

2、欧式几何平面距离

3、切比雪夫距离

 

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄