A*算法详尽的入门教程

一： 为什么我们需要A*算法

求最短路径或者最小代价的算法有很多。其本质就是图的搜索策略。图的直接搜索方法有很多种，比较典型的是广度优先搜索、深度优先搜索。所谓的广度优先搜索是每到达一个节点就优先遍历该节点的所有相邻节点。而对应的深度优先搜索是指一直延伸到从未达到过的节点。基于以上两种基本思想的最短路径算法有Dijkstra算法和Floyd算法。当搜索完毕也遍历了整张图，其时间开销是很大的，尤其是在图非常大的时候这种时间复杂度是不能接受的。上述算法之所以时间开销大是因为在搜索的过程并没有对当前状态进行评估，因此是基于穷搜的。另一种思路就是在搜索的过程中利用一些合适的评估函数来进行剪枝，首先去除那些不可能产生最优解的分支。这就是所谓的启发式搜索。而A*算法就是基于这种思想的搜索算法。

二： 什么是A*算法

A*算法是一个可采纳的最好优先算法（BFS）。

A*算法的估价函数可表示为：

f'(n)= g'(n) + h'(n)

这里，f'(n)是估价函数，g'(n)是起点到节点n的最短路径值，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。

举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最坏的A*算法。

 

三： A*算法的过程

上节简单介绍了A*算法的基本原理。那么对于一个具体的问题怎么用A*算法呢？下面给出A*算法的执行过程。

1.   初始化

将开始节点放入开放列表(开始节点的F和G值都视为0);

2.   重复以下过程

①     ：在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点;

②     ：把当前节点从开放列表删除,