A*算法

背景

有一次面试,做笔试题,里面有一道题是A*算法,当时没有接触过,就没有做出来.

A*算法是什么

A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度

介绍A*算法之前先介绍其他的算法

广度优先搜索

广度优先搜索以广度做为优先级进行搜索。

从起点开始，首先遍历起点周围邻近的点，然后再遍历已经遍历过的点邻近的点，逐步的向外扩散，直到找到终点。

这种算法就像洪水(Flood fill)一样向外扩张。

广度优先搜索算法会遍历所有的点，这通常没有必要。对于有明确终点的问题来说，一旦到达终点便可以提前终止算法。

在执行算法的过程中，每个点需要记录达到该点的前一个点的位置(父节点)。这样做之后，一旦到达终点，便可以从终点开始，反过来顺着父节点的顺序找到起点，由此就构成了一条路径。

Dijkstra算法

Dijkstra算法用来寻找图形中节点之间的最短路径。

考虑这样一种场景，在一些情况下，图形中相邻节点之间的移动代价并不相等。例如，游戏中的一幅图，既有平地也有山脉，那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。

在Dijkstra算法中，需要计算每一个节点距离起点的总移动代价。同时，还需要一个优先队列结构。对于所有待遍历的节点，放入优先队列中会按照代价进行排序。

在算法运行的过程中，每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。

最佳优先搜索

在一些情况下，如果我们可以预先计算出每个节点到终点的距离，则我们可以利用这个信息更快的到达终点。

其原理也很简单。与Dijkstra算法类似，我们也使用一个优先队列，但此时以每个节点到达终点的距离作为优先级，每次始终选取到终点移动代价最小(离终点最近)的节点作为下一个遍历的节点。这种算法称之为最佳优先(Best First)算法。

最佳优先搜索算法的缺点: 如果起点和终点之间存在障碍物，则最佳优先算法找到的很可能不是最短路径

A*算法

A*算法实际上是综合上面这些算法的特点于一身的.

A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。公式表示为： f(n)=g(n)+h(n)，其中， f(n)是从初始状态经由状态n到目标状态的代价估计，g(n) 是在状态空间中从初始状态到状态n的实际代价，h(n)是从状态n到目标状态的最佳路径的估计代价。对于路径搜索问题，状态就是图中的节点，代价就是距离。

A* 算法具体实现可以网上找,因为我不是专门研究算法的,这里我只介绍了一下A*算法的大概情况,对于我个人来说,只需要了解一下算法的思路,达到可以举一反三的效果我就满足了

本文参考:

• A Star Algorithm 总结与实现
• 路径规划之 A* 算法 本文文字也大部分取自于此