本文作者:心月

A*算法实例详解

心月IT博客 2019-02-26
摘要:A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度。

A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度。

A*算法描述:

A*改变它自己行为的能力基于启发式代价函数,启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中,你并不真正需要得到最好的路径,仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么,或者运行游戏的机器有多快。 假设你的游戏有两种地形,平原和山地,在平原中的移动代价是1而在山地的是3,那么A星算法就会认为在平地上可以进行三倍于山地的距离进行等价搜寻。 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较,这并不比把3和1比较差。然而,在山地上行动有时可能会优于绕过山脚下进行行动。所以花费更多时间寻找一个绕过山的算法并不经常是可靠的。 同样的,想要达成这样的目标,你可以通过减少在山脚下的搜索行为来打到提高A星算法的运行速率。若想如此可以将A星算法的山地行动耗费从3调整为2即可。这两种方法都会给出可靠地行动策略。

A*算法实例详解:

A*算法详解

在地图中每个方格都有两个属性,一是方格是否可通行,二是指向其父结点的指针。

A星算法中有几个相当重要的元素:

第一个就是指向其父结点的指针。

第二个就是OPEN表。

第三个就是CLOSE表,这两张表的具体作用我们在后面边用边介绍。

第四个就是每个结点的F值(F值相当于图结构中的权值) 。F = H + G 其中H值为从网格上当前方格移动到终点的预估移动耗费。这经常被称为启发式的,可能会让你有点迷惑。

这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度,因为路上可能存在各种障碍(墙,水,等等)。虽然本文只提供了一种计算H的方法,但是你可以在网上找到很多其他的方法。

我们定义H值为 终点所在行减去当前格所在行的绝对值 与 终点所在列减去当前格所在列的绝对值;

A*算法详解

而G值为从其父方格移动到当前格的预估移动耗费,在这里我们设定一个基数10,每个H和G都要乘以10,这样方便观察

 

开始搜索:首先,我们将起点的父结点设置为NULL,然后将起点的G值设置为0,再装进open表里面,然后将起点作为父结点的周围4个点20,28,30,38(因为我们地图只能走4个方向,如果是8方向,则要加个点进去)

都加进open列表里面,并计算每个结点的H值。然后再将起点从open列表删除,放进close表中。

我们将放进close表的所有方格都用浅蓝色线条进行框边处理,所以这次搜索以后,图片变为如下格式,其中箭头代表的是其父结点

A*算法实例详解

其中每个格子的左下方为G值,右下方为H值,左上方为H值。我们拿28号格子为例来讲解一写F值的算法,首先因为终点33在4行7列,而28在4行2列,则行数相差为0,列数相差为5,总和为5,

再乘以我们先前定的基数10,所以H值为50,又因为从28的父结点29移动到28,长度为1格,而29号为起点,G值为0,所以在父亲结点29的基础上移动到28所消耗的G值为(0 + 1) *10 = 10,

0为父亲结点的G值,1为从29到28的消耗。当前OPEN表中的值: 20,28,30,38     当前CLOSE表中的值: 29

现在我们开始寻找OPEN列表中F值最低的,得出结点30的F值最低,且为40,然后将结点30从OPEN表中删除,然后再加入到CLOSE表中,然后在判断结点30周围4个结点,因为结点31为障碍,

结点29存在于CLOSE表中,我们将不处理这两点,只将21和39号结点加入OPEN表中,添加完后地图变为下图样式

当前OPEN表中的值: 20,28,38,21,39   当前CLOSE表中的值: 29,30

A*算法实例详解

接着我们重复上面的过程,寻找OPEN表中F值为低的值。我们发现OPEN表中所有结点的F值都为60,我们随即取一个结点。这里我们直接取最后添加进OPEN表中的结点,

这样方便访问(因为存在这样的情况,所有从一个点到另外一个点的最短路径可能不只一条),我们取结点39,将他从OPEN表中删除,并添加进CLOSE表中。然后观察39号

结点周围的4个结点。因为40号结点为障碍,所以我们不管它,而30号结点已经存在与OPEN表中了。所以我们要比较下,假设39号结点为30号结点的父结点,30号结点的G值会不会更小?

如果更小的话我们将30结点的父结点改为39号。这里我们以39号结点为父结点,得出30号结点的新G值为20。而30号结点原来的G值为10,并不比原来的小,所以我们不对30号进行任何操作。

同样的对38号结点进行上述操作后我们也不对它进行任何操作,接着我们把48号结点添加进OPEN表中,添加完后地图变为下图样式

当前OPEN表中的值: 20,28,38,21,48   当前CLOSE表中的值: 29,30,39

A*算法实例详解

以后的过程中我们都重复这样的过程,一直到遍历到了最后终点,通过遍历父结点编号,我们能够得出一条最短路径。

这里我再讲出一个特例,然后基本A星算法就没问题了。上面的最后一推导中,我们在观察39号结点时,发现他周围已经有结点在OPEN表中了,

我说"比较下假设39号结点为30号结点的父结点,30号结点的G值会不会更小,如果更小的话我们将30结点的父结点改为39号"。

但是刚才没有遇到G值更小的情况,所以这里我假设出一种G值更小的情况。

然后让大家知道该怎么操作,假设以39号为父结点,我们得出的30号的新G值为5(只是假设),比30号的原G值10还要小,所以我们要修改路径,改变30号的箭头,本来他是指向29号结点的,我们现在让他指向39号结点,38号结点的操作也一样

好了,A星算法的大体思路就是这样了,对于8方向的地图来说,唯一的改变就是G值方面,在上下左右,我们的G值是加10,但是在斜方向我们要加14,其他的和上面讲的一样~~~:)

文章版权及转载声明:

作者:心月 本文地址:http://www.xinyueseo.com/algorithm/140.html发布于 2019-09-07
文章转载或复制请以超链接形式并注明出处心月IT博客

分享到:
赞(

发表评论

快捷输入:

    评论列表 (有 0 条评论,人围观)参与讨论