算法集锦

算法集锦之路径规划算法(3):A*算法

 
 
AMadmin的头像
算法集锦之路径规划算法(3):A*算法
AMadmin 发表于 2017年08月13日 星期日 10:51
 

A*(A star)是在地图中找到两个位置之间最短路径的最流行方法之一。 A*于1968年开发,结合了Dijsktra算法以及启发式搜索算法的特点。


A*算法的基本思路是从起点S开始,逐步建立一个“闭合列表(Closed List)”来记录已经评估的区域,以及一个“边缘列表”来记录已经评估的区域的相邻区域。
这样,“闭合列表”是算法进行了探索和评估的所有位置的记录。“边缘列表”通常被称为“开放列表(Open List)”,它记录了紧邻“封闭列表”的所有位置的列表。
对于“闭合列表”和“开放列表”中的每个位置,将计算从起点S移动到该位置的距离g,以及从该位置到终点E的估算距离h。算法将依据f=g+h的值,从“开放列表”中选择具有最小f的位置作为下一个搜索位置,放进闭合列表,并且重新计算“开放列表”中其他位置的f值。当终点E出现在闭合列表中,则算法结束。



图1 目前的位置是蓝色的正方形,现在是封闭列表的一部分。围绕蓝色的绿色方块是边缘部分,将从中选择下一步的可能探索位置。



图2 随着路径的发展,封闭和开放列表逐步增长。请注意,这条路径允许在角落斜线转弯(如果灰色区域是像墙一样的障碍,那么这条路可能是无效的)。



图3 当不允许在角落斜线转弯时,该路径将更适合于避免障碍。


用于评估A *中的距离的启发式是:
     f(n)= g(n)+ h(n)
其中g(n)表示从起始点到任何顶点n的路径的成本(距离),h(n)表示从顶点n到目标的估计成本。

Manhattan距离和Euclidean距离(直线距离)是用于当前点到终点的估算成本h(n)的常用方法。
         x2 =目标位置的坐标
         x1 =当前位置的坐标
         y2 =目标位置的坐标
         y1 =当前位置的坐标
         dx = | x2 - x1 |
         dy = | y2 - y1 |
Manhattan距离 = dx+dy
Euclidean距离 = sqrt(dx的平方 + dy的平方)


A*算法相当简单。有两个集合:OPEN和CLOSED。 OPEN集合包含那些作为检查候选的结点。最初,OPEN集只包含一个元素:起始位置。 CLOSED集合包含已经被检查的那些结点。最初,CLOSED集是空的。在图形上,CLOSED集合是访问区域的“内部”,OPEN集合是“前沿”。每个结点还保留指向其父结点的指针,以便确定从起点移动到该结点的路径。

采用一个主循环反复合从OPEN中找出最好的结点N(f值最小的结点),作为下一个带检测的点:
1)如果N是目标结点,那么算法就结束了。
2)否则,把结点N从OPEN中删除并添加到CLOSED。然后,逐个检查N的所有邻居Ni:
a)若Ni无法到达胡或已经在CLOSED集合中,那么不用管它。
b)如果Ni不在OPEN中,则将该Ni添加到OPEN中, 并将该Ni的父结点设为N,同时保存Ni的g和f值,g(Ni)的路径开销将被设置为g(N)+cost(N,Ni)[从N移动到Ni的代价];
c)如果Ni已经在OPEN中, 则判断若经由N到达Ni的g值是否小于原来保存的g值,若小于,则需要将Ni的父结点设为N,并重新设置Ni的g和f值。



图5 A*的演示(采用Manhattan距离,并且不允许角落斜线通过)


点击下面的蓝色的阅读全文,观看一个详细的A*算法例子。

阅读原文