导购网站的seo怎么做,网站导入页欣赏,网站快速排名,网站建设 珠海算法介绍
A*#xff08;念做#xff1a;A Star#xff09;算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。本文在讲解算法的同时也会提供Python语言的代码实现#xff0c;并会借助matplotlib库动态的展示算法的运算过程。
A*算法最初发表于1968年念做A Star算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。本文在讲解算法的同时也会提供Python语言的代码实现并会借助matplotlib库动态的展示算法的运算过程。
A*算法最初发表于1968年由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。
由于借助启发函数的引导A*算法通常拥有更好的性能。
广度优先搜索
为了更好的理解A*算法我们首先从广度优先Breadth First算法讲起。
正如其名称所示广度优先搜索以广度做为优先级进行搜索。
从起点开始首先遍历起点周围邻近的点然后再遍历已经遍历过的点邻近的点逐步的向外扩散直到找到终点。
这种算法就像洪水Flood fill一样向外扩张算法的过程如下图所示 在上面这幅动态图中算法遍历了图中所有的点这通常没有必要。对于有明确终点的问题来说一旦到达终点便可以提前终止算法下面这幅图对比了这种情况 在执行算法的过程中每个点需要记录达到该点的前一个点的位置 -- 可以称之为父节点。这样做之后一旦到达终点便可以从终点开始反过来顺着父节点的顺序找到起点由此就构成了一条路径。
Dijkstra算法
Dijkstra算法是由计算机科学家Edsger W. Dijkstra在1956年提出的。
Dijkstra算法用来寻找图形中节点之间的最短路径。
考虑这样一种场景在一些情况下图形中相邻节点之间的移动代价并不相等。例如游戏中的一幅图既有平地也有山脉那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。
在Dijkstra算法中需要计算每一个节点距离起点的总移动代价。同时还需要一个优先队列结构。对于所有待遍历的节点放入优先队列中会按照代价进行排序。
在算法运行的过程中每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。
下面对比了不考虑节点移动代价差异的广度优先搜索与考虑移动代价的Dijkstra算法的运算结果 当图形为网格图并且每个节点之间的移动代价是相等的那么Dijkstra算法将和广度优先算法变得一样。 最佳优先搜索
在一些情况下如果我们可以预先计算出每个节点到终点的距离则我们可以利用这个信息更快的到达终点。
其原理也很简单。与Dijkstra算法类似我们也使用一个优先队列但此时以每个节点到达终点的距离作为优先级每次始终选取到终点移动代价最小离终点最近的节点作为下一个遍历的节点。这种算法称之为最佳优先Best First算法。
这样做可以大大加快路径的搜索速度如下图所示 但这种算法会不会有什么缺点呢答案是肯定的。
因为如果起点和终点之间存在障碍物则最佳优先算法找到的很可能不是最短路径下图描述了这种情况。 A*算法
对比了上面几种算法最后终于可以讲解本文的重点A*算法了。
下面的描述我们将看到A*算法实际上是综合上面这些算法的特点于一身的。
A*算法通过下面这个函数来计算每个节点的优先级。 f(n)g(n)h(n)
其中
f(n) 是节点n的综合优先级。当我们选择下一个要遍历的节点时我们总会选取综合优先级最高值最小的节点。g(n) 是节点n距离起点的代价。h(n) 是节点n距离终点的预计代价这也就是A*算法的启发函数。关于启发函数我们在下面详细讲解。
A*算法在运算过程中每次从优先队列中选取f(n)值最小优先级最高的节点作为下一个待遍历的节点。
另外A*算法使用两个集合来表示待遍历的节点与已经遍历过的节点这通常称之为open_set和close_set。
完整的A*算法描述如下
* 初始化open_set和close_set
* 将起点加入open_set中并设置优先级为0优先级最高
* 如果open_set不为空则从open_set中选取优先级最高的节点n* 如果节点n为终点则* 从终点开始逐步追踪parent节点一直达到起点* 返回找到的结果路径算法结束* 如果节点n不是终点则* 将节点n从open_set中删除并加入close_set中* 遍历节点n所有的邻近节点* 如果邻近节点m在close_set中则* 跳过选取下一个邻近节点* 如果邻近节点m也不在open_set中则* 设置节点m的parent为节点n* 计算节点m的优先级* 将节点m加入open_set中
启发函数
上面已经提到启发函数会影响A*算法的行为。
在极端情况下当启发函数h(n)始终为0则将由g(n)决定节点的优先级此时算法就退化成了Dijkstra算法。如果h(n)始终小于等于节点n到终点的代价则A*算法保证一定能够找到最短路径。但是当h(n)的值越小算法将遍历越多的节点也就导致算法越慢。如果h(n)完全等于节点n到终点的代价则A*算法将找到最佳路径并且速度很快。可惜的是并非所有场景下都能做到这一点。因为在没有达到终点之前我们很难确切算出距离终点还有多远。如果h(n)的值比节点n到终点的代价要大则A*算法不能保证找到最短路径不过此时会很快。在另外一个极端情况下如果h(n)相较于g(n)大很多则此时只有h(n)产生效果这也就变成了最佳优先搜索。
由上面这些信息我们可以知道通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况我们可能未必需要最短路径而是希望能够尽快找到一个路径即可。这也是A*算法比较灵活的地方。
对于网格形式的图有以下这些启发函数可以使用
如果图形中只允许朝上下左右四个方向移动则可以使用曼哈顿距离Manhattan distance。如果图形中允许朝八个方向移动则可以使用对角距离。如果图形中允许朝任何方向移动则可以使用欧几里得距离Euclidean distance。
关于距离
曼哈顿距离
如果图形中只允许朝上下左右四个方向移动则启发函数可以使用曼哈顿距离它的计算方法如下图所示 计算曼哈顿距离的函数如下这里的D是指两个相邻节点之间的移动代价通常是一个固定的常数。
function heuristic(node) dx abs(node.x - goal.x)dy abs(node.y - goal.y)return D * (dx dy)
对角距离
如果图形中允许斜着朝邻近的节点移动则启发函数可以使用对角距离。它的计算方法如下 计算对角距离的函数如下这里的D2指的是两个斜着相邻节点之间的移动代价。如果所有节点都正方形则其值就是2∗D。
function heuristic(node) dx abs(node.x - goal.x)dy abs(node.y - goal.y)return D * (dx dy) (D2 - 2 * D) * min(dx, dy)
欧几里得距离
如果图形中允许朝任意方向移动则可以使用欧几里得距离。
欧几里得距离是指两个节点之间的直线距离因此其计算方法也是我们比较熟悉的(p2.x−p1.x)2(p2.y−p1.y)2。其函数表示如下
function heuristic(node) dx abs(node.x - goal.x)dy abs(node.y - goal.y)return D * sqrt(dx * dx dy * dy)
算法实现
虽然前面介绍了很多内容但实际上A*算法并不复杂实现起来也比较简单。
下面我们给出一个Python语言的代码示例。
之所以使用Python语言是因为我们可以借助matplotlib库很方便的将结果展示出来。在理解了算法之后通过其他语言实现也并非难事。 算法的源码可以到我的github上下载paulQuei/a-star-algorithm。 我们的算法演示的是在一个二维的网格图形上从起点找寻终点的求解过程。
坐标点与地图
首先我们创建一个非常简单的类来描述图中的点相关代码如下
# point.pyimport sysclass Point:def __init__(self, x, y):self.x xself.y yself.cost sys.maxsize
接着我们实现一个描述地图结构的类。为了简化算法的描述:
我们选定左下角坐标[0, 0]的点是算法起点右上角坐标[size - 1, size - 1]的点为要找的终点。
为了让算法更有趣我们在地图的中间设置了一个障碍并且地图中还会包含一些随机的障碍。该类的代码如下
# random_map.pyimport numpy as npimport pointclass RandomMap:def __init__(self, size50): ①self.size sizeself.obstacle size//8 ②self.GenerateObstacle() ③def GenerateObstacle(self):self.obstacle_point []self.obstacle_point.append(point.Point(self.size//2, self.size//2))self.obstacle_point.append(point.Point(self.size//2, self.size//2-1))# Generate an obstacle in the middlefor i in range(self.size//2-4, self.size//2): ④self.obstacle_point.append(point.Point(i, self.size-i))self.obstacle_point.append(point.Point(i, self.size-i-1))self.obstacle_point.append(point.Point(self.size-i, i))self.obstacle_point.append(point.Point(self.size-i, i-1))for i in range(self.obstacle-1): ⑤x np.random.randint(0, self.size)y np.random.randint(0, self.size)self.obstacle_point.append(point.Point(x, y))if (np.random.rand() 0.5): # Random boolean ⑥for l in range(self.size//4):self.obstacle_point.append(point.Point(x, yl))passelse:for l in range(self.size//4):self.obstacle_point.append(point.Point(xl, y))passdef IsObstacle(self, i ,j): ⑦for p in self.obstacle_point:if ip.x and jp.y:return Truereturn False
这段代码说明如下
构造函数地图的默认大小是50x50设置障碍物的数量为地图大小除以8调用GenerateObstacle生成随机障碍物在地图的中间生成一个斜着的障碍物随机生成其他几个障碍物障碍物的方向也是随机的定义一个方法来判断某个节点是否是障碍物
算法主体
有了基本的数据结构之后我们就可以开始实现算法主体了。
这里我们通过一个类来封装我们的算法。
首先实现一些算法需要的基本函数它们如下
# a_star.pyimport sys
import timeimport numpy as npfrom matplotlib.patches import Rectangleimport point
import random_mapclass AStar:def __init__(self, map):self.mapmapself.open_set []self.close_set []def BaseCost(self, p):x_dis p.xy_dis p.y# Distance to start pointreturn x_dis y_dis (np.sqrt(2) - 2) * min(x_dis, y_dis)def HeuristicCost(self, p):x_dis self.map.size - 1 - p.xy_dis self.map.size - 1 - p.y# Distance to end pointreturn x_dis y_dis (np.sqrt(2) - 2) * min(x_dis, y_dis)def TotalCost(self, p):return self.BaseCost(p) self.HeuristicCost(p)def IsValidPoint(self, x, y):if x 0 or y 0:return Falseif x self.map.size or y self.map.size:return Falsereturn not self.map.IsObstacle(x, y)def IsInPointList(self, p, point_list):for point in point_list:if point.x p.x and point.y p.y:return Truereturn Falsedef IsInOpenList(self, p):return self.IsInPointList(p, self.open_set)def IsInCloseList(self, p):return self.IsInPointList(p, self.close_set)def IsStartPoint(self, p):return p.x 0 and p.y 0def IsEndPoint(self, p):return p.x self.map.size-1 and p.y self.map.size-1
这里的函数说明如下
__init__类的构造函数。BaseCost节点到起点的移动代价对应了上文的g(n)。HeuristicCost节点到终点的启发函数对应上文的h(n)。由于我们是基于网格的图形所以这个函数和上一个函数用的是对角距离。TotalCost代价总和即对应上面提到的f(n)。IsValidPoint判断点是否有效不在地图内部或者障碍物所在点都是无效的。IsInPointList判断点是否在某个集合中。IsInOpenList判断点是否在open_set中。IsInCloseList判断点是否在close_set中。IsStartPoint判断点是否是起点。IsEndPoint判断点是否是终点。
有了上面这些辅助函数就可以开始实现算法主逻辑了相关代码如下
# a_star.py
def RunAndSaveImage(self, ax, plt):start_time time.time()start_point point.Point(0, 0)start_point.cost 0self.open_set.append(start_point)while True:index self.SelectPointInOpenList()if index 0:print(No path found, algorithm failed!!!)returnp self.open_set[index]rec Rectangle((p.x, p.y), 1, 1, colorc)ax.add_patch(rec)self.SaveImage(plt)if self.IsEndPoint(p):return self.BuildPath(p, ax, plt, start_time)del self.open_set[index]self.close_set.append(p)# Process all neighborsx p.xy p.yself.ProcessPoint(x-1, y1, p)self.ProcessPoint(x-1, y, p)self.ProcessPoint(x-1, y-1, p)self.ProcessPoint(x, y-1, p)self.ProcessPoint(x1, y-1, p)self.ProcessPoint(x1, y, p)self.ProcessPoint(x1, y1, p)self.ProcessPoint(x, y1, p)
这段代码应该不需要太多解释了它就是根据前面的算法逻辑进行实现。为了将结果展示出来我们在算法进行的每一步都会借助于matplotlib库将状态保存成图片。
上面这个函数调用了其他几个函数代码如下
# a_star.py
def SaveImage(self, plt):millis int(round(time.time() * 1000))filename ./ str(millis) .pngplt.savefig(filename)def ProcessPoint(self, x, y, parent):if not self.IsValidPoint(x, y):return # Do nothing for invalid pointp point.Point(x, y)if self.IsInCloseList(p):return # Do nothing for visited pointprint(Process Point [, p.x, ,, p.y, ], , cost: , p.cost)if not self.IsInOpenList(p):p.parent parentp.cost self.TotalCost(p)self.open_set.append(p)def SelectPointInOpenList(self):index 0selected_index -1min_cost sys.maxsizefor p in self.open_set:cost self.TotalCost(p)if cost min_cost:min_cost costselected_index indexindex 1return selected_indexdef BuildPath(self, p, ax, plt, start_time):path []while True:path.insert(0, p) # Insert firstif self.IsStartPoint(p):breakelse:p p.parentfor p in path:rec Rectangle((p.x, p.y), 1, 1, colorg)ax.add_patch(rec)plt.draw()self.SaveImage(plt)end_time time.time()print( Algorithm finish in, int(end_time-start_time), seconds)
这三个函数应该是比较容易理解的
SaveImage将当前状态保存到图片中图片以当前时间命名。ProcessPoint针对每一个节点进行处理如果是没有处理过的节点则计算优先级设置父节点并且添加到open_set中。SelectPointInOpenList从open_set中找到优先级最高的节点返回其索引。BuildPath从终点往回沿着parent构造结果路径。然后从起点开始绘制结果结果使用绿色方块每次绘制一步便保存一个图片。
测试入口
最后是程序的入口逻辑使用上面写的类来查找路径
# main.pyimport numpy as np
import matplotlib.pyplot as pltfrom matplotlib.patches import Rectangleimport random_map
import a_starplt.figure(figsize(5, 5))map random_map.RandomMap() ①ax plt.gca()
ax.set_xlim([0, map.size]) ②
ax.set_ylim([0, map.size])for i in range(map.size): ③for j in range(map.size):if map.IsObstacle(i,j):rec Rectangle((i, j), width1, height1, colorgray)ax.add_patch(rec)else:rec Rectangle((i, j), width1, height1, edgecolorgray, facecolorw)ax.add_patch(rec)rec Rectangle((0, 0), width 1, height 1, facecolorb)
ax.add_patch(rec) ④rec Rectangle((map.size-1, map.size-1), width 1, height 1, facecolorr)
ax.add_patch(rec) ⑤plt.axis(equal) ⑥
plt.axis(off)
plt.tight_layout()
#plt.show()a_star a_star.AStar(map)
a_star.RunAndSaveImage(ax, plt) ⑦
这段代码说明如下
创建一个随机地图设置图像的内容与地图大小一致绘制地图对于障碍物绘制一个灰色的方块其他区域绘制一个白色的的方块绘制起点为蓝色方块绘制终点为红色方块设置图像的坐标轴比例相等并且隐藏坐标轴调用算法来查找路径
由于我们的地图是随机的所以每次运行的结果可能会不一样下面是我的电脑上某次运行的结果 如果感兴趣这篇文章中的动图是如何制作的请看我的另外一篇文章使用Matplotlib绘制3D图形 - 制作动图。 算法变种
A*算法有不少的变种这里我们介绍最主要的几个。
更多的内容请以访问维基百科A* Variants。
ARA*
ARA 全称是Anytime Repairing A*也称为Anytime A。
与其他Anytime算法一样它具有灵活的时间成本即使在它结束之前被中断也可以返回路径查找或图形遍历问题的有效解决方案。方法是在逐步优化之前生成快速非最优的结果。
在现实世界的规划问题中问题的解决时间往往是有限的。与时间相关的规划者对这种情况都会比较熟悉他们能够快速找到可行的解决方案然后不断努力改进直到时间用完为止。
启发式搜索ARA*算法它根据可用的搜索时间调整其性能边界。它首先使用松散边界快速找到次优解然后在时间允许的情况下逐渐收紧边界。如果有足够的时间它会找到可证明的最佳解决方方案。在改进其约束的同时ARA*重复使用以前的搜索工作因此比其他随时搜索方法更有效。
与A*算法不同Anytime A*算法最重要的功能是它们可以被停止然后可以随时重启。该方法使用控制管理器类来处理时间限制以及停止和重新启动A*算法以找到初始的可能是次优的解决方案然后继续搜索改进的解决方案直到达到可证明的最佳解决方案。
关于ARA*的更多内容可以阅读这篇论文
ARA - Anytime A with Provable Bounds on Sub-Optimality。
D*
D*是Dynamic A*的简写其算法和A*类似不同的是其代价的计算在算法运行过程中可能会发生变化。
D*包含了下面三种增量搜索算法
原始的D*由Anthony Stentz发表。Focussed D*由Anthony Stentz发表是一个增量启发式搜索算法结合了A*和原始D*的思想。D Lite是由Sven Koenig和Maxim Likhachev基于LPA构建的算法。
所有三种搜索算法都解决了相同的基于假设的路径规划问题包括使用自由空间假设进行规划。在这些环境中机器人必须导航到未知地形中的给定目标坐标。它假设地形的未知部分例如它不包含障碍物并在这些假设下找到从当前坐标到目标坐标的最短路径。
然后机器人沿着路径行进。当它观察到新的地图信息例如以前未知的障碍物时它会将信息添加到其地图中并在必要时将新的最短路径从其当前坐标重新添加到给定的目标坐标。它会重复该过程直到达到目标坐标或确定无法达到目标坐标。在穿越未知地形时可能经常发现新的障碍因此重新计划需要很快。增量启发式搜索算法通过使用先前问题的经验来加速搜索当前问题从而加速搜索类似搜索问题的序列。假设目标坐标没有改变则所有三种搜索算法都比重复的A*搜索更有效。
D*及其变体已广泛用于移动机器人和自动车辆导航。当前系统通常基于D* Lite而不是原始D*或Focussed D*。
关于D*的更多内容可以阅读这两篇文章
Project Fast Replanning Incremental Heuristic SearchReal-Time Replanning in Dynamic and Unknown Environments
Field D*
Field D*扩展了D*和D* Lite是一种基于插值 interpolation-based 的规划算法它使用线性插值来有效地生成低成本路径从而消除不必要的转向。
在给定线性插值假设的情况下路径是最优的并且在实践中非常有效。该算法目前被各种现场机器人系统使用。
关于Field D*的详细内容可以看下面这篇论文
Field D*: An Interpolation-based Path Planner and Replanner
Block A*
Block A*扩展自A*但它操作是一块block单元而不是单个单元。
其open_set中的每个条目都是已到达但尚未扩展的块或者需要重新扩展的块。
open_set中块的优先级称为其堆值heap value。与A*类似Block A*中的基本循环是删除具有最低堆值的条目并将其展开。在扩展期间使用LDDB来计算正在扩展的块中的边界单元的g值。
LDDB是一种新型数据库它包含了本地邻域边界点之间的距离。
关于Block A*的更多内容可以看下面这篇论文
Block A*: Database-Driven Search with Applications in Any-angle Path-Planning原文链接 本文为云栖社区原创内容未经允许不得转载。
