Skip to content

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*算法的大概情况,对于我个人来说,只需要了解一下算法的思路,达到可以举一反三的效果我就满足了

本文参考: