A(star)算法原理讲解以及程序实现(基于Python)

沉默的老大

A*搜索算法原理及其程序实现去我的个人博客观看，观感更佳哦，😙😙运行环境推荐anaconda3，集成了常用的用于科学计算的包，以及对应的Python解释器(本例使用的解释器版本为3.9.12)编辑器：VScode摘要本文将以迷宫探索最优路径为例，讲解A*搜索算法原理及其程序实现。在原理讲解部分，首先从为什么要使用A*搜索算法和A*搜索算法的全局最优逻辑出发，讲解A*算法的原理。其次对A*的行动函数g(n)和启发函数h(n)的细节进行了讲解说明，并补充了启发函数的选择对于A*算法的影响。在程序实现部分，首先从程序流程框图出发，解释A*算法的流程。其次按函数的类划分并讲解主要代码，接着展示程序的运行结果，最后对A*算法进行总结分析。原理讲解为什么要使用A*搜索算法？搜索算法的核心是从起点出发，找到一条到达目标的最优（路径最短/成本最低/两者兼具）的路径。根据不同需求，我们通常会选择：广度优先搜索（BFS）、Dijkstra算法（统一成本搜索）和贪婪优先搜索之一，下面我们逐个分析其优劣。广度优先算法：不考虑每一步的移动成本，不断拓展边界，直到边界到达目标点，通常耗费大量时间。Dijkstra算法：以BFS为基础，只考虑每一点的总移动成本，没有解决BFS耗费大量时间的问题。贪婪优先搜索：只考虑到达终点的估计距离，能较快寻找到目标，但是无法保证路线全局最优。A*搜索算法：以BSF为基础，综合考虑了总移动成本和到达终点的估计距离，巧妙地叠加了Dijkstra算法的成本最低和贪婪优先搜索的速度最优，具有更好的性能。下面是A*算法的核心公式：f(n)=g(n)+h(n)f(n)=g(n)+h(n)f(n)=g(n)+h(n)说明：f(n)是总的预期成本，g(n)是当前点到起点的总移动成本，h(n)是当前点到目标点的预期代价A*搜索算法的全局最优逻辑首先，对于搜索算法来说，想要减少搜索的时间，那就必须要在搜索最优路径时搜索尽量少的点，最好搜索的全部节点恰好就是我们的全局最优路径。但显然，像贪婪优先搜索那样，只考虑当前点到目标点的预期距离的话，往往只能寻找到局部最优。换句话说，贪婪优先算法只考虑单一的：当前点到目标点的估计距离，这显然不足以作为全局最优的参考指标。但是它赋予了程序有目的地前往终点方向的能力而我们知道，BFS、Dijkstra实质上是对所有节点进行遍历，其中后者是对前者的优化，保证了起点到每一个中间点都是成本最优的选择。那我们结合一下Dijkstra（保障当前点对起点是成本最优的）和贪婪优先搜索（保障当前点到终点的方向是最优的）就可以构建一个新的参考指标：用于保证每一次从当前点选择下一个节点的时候都是全局最优的。对行动函数g(n)的细节说明（可以简单理解g是小兵）在A*算法中对于g(n)，也就是从起点到当前点的总移动代价（沉没成本），如果我们只考虑上下左右四个方向的话，并不需要额外考虑每一步行动的代价（因为每一步都是相同的），但是如果我们从上下左右和四个边角都能被行动，那我们就需要考虑走斜边和直上直下的代价差异。本样例中，所有的节点都是正方形，从而可知走斜边与直上直下的代价比值应为2:1\sqrt2:12​:1我们为了方便计算，取1.4：1作为走斜边和直上直下的代价比值对启发函数h(n)的讲解（可以简单理解h是领导）在A*算法中对于h(n)，也就是对当前点到目标点的预期代价估计通常采用“距离”作为度量。在二维地图中，我们讨论两点间距离常用的方式有两种。曼哈顿距离c=∣x2−x1∣+∣y2−y1∣c=|x_{2}-x_{1}|+|y_{2}-y_{1}|c=∣x2​−x1​∣+∣y2​−y1​∣曼哈顿距离用来标明两个点在标准坐标系上的绝对轴距总和，简单来理解就是：直角三角形的两直角边之和欧式距离d=（x2−x1）2+（y2−y1）2d=\sqrt{{（x_{2}-x_{1}）^{2}+（y_{2}-y_{1}）^{2}}}d=（x2​−x1​）2+（y2​−y1​）2​欧式距离用来标明两个点在标准坐标系上的绝对距离，简单来理解就是：直角三角形的斜边在接下来的代码实现中，因为曼哈顿距离不需要开方，计算较为简便，因此本例选用曼哈顿距离作为启发函数的参考指标。补充：启发函数的选择对算法的影响（了解）f(n)=g(n)+h(n)f(n)=g(n)+h(n)f(n)=g(n)+h(n)情况算法结果h(n)=0A*退化为Dijkstra算法保证能找到最短路径，但时间花费较大h(n)=实际代价仅拓展必要节点时间和路径都最佳h(n)>>g(n)A*算法退化到贪婪优先不保证全局路径最优，但速度很快程序流程图地图初始化：设置地图大小、起点终点、障碍物。遍历待测节点：将起点放入待测列表（open_list）中，进而让A*算法开始运行，计算并存储列表中每一个节点的"f(n)"。定位正在检测点：查找"f(n)"最小的节点，并把它定位为正在检测的点（select_current）。邻点检测：A*算法的核心，通过对邻点属性的判断和对预期总移动成本的权衡来选择下一个节点移动到已测点集：将已经检测过但是没被选择的节点放入已测列表中，保证不会重复搜索找到终点：找到终点后，由终点向起点进行最短路径的回溯，并通过调用pillow库，将结果导出为图片AStar类是整个算法的关键，内部包括了A*算法的初始化、最优点选择、邻点检测、节点判断和路径寻找功能的实现初始化参数通过构造函数，将地图属性：地图大小、起点、终点和障碍物读入，初始化A*算法的参数：def__init__(self,startoint,endoint,map2d:Map2D):self.path=[] self.closed_list=[]self.open_list=[]self.start=startself.end=endself.map2d=map2d1234567最优点选择遍历待检测队列（open_list），找到f值最小的节点（全局最优节点），然后返回全局最优节点defselect_current(self):min_f=sys.maxsizenode_temp=Nonefornodeinself.open_list:ifnode.fNone:self.x=xself.y=y#重载“==”运算符，(x1,y1)==(x2,y2)，当且仅当x1=x2，y1=y2def__eq__(self,other)->bool:returnself.x==other.xandself.y==other.yclassMap2D:def__init__(self,height,width)->None:self.height=heightself.width=width#width可以看成二维地图的行，height可以看成二维地图的列self.data=[["⬜"for_inrange(width)]for_inrange(height)]#将地图数据用文本导出defshow(self,file_name="output.txt")->None:withopen(file_name,'w',encoding='utf-8')asfile:forrowinself.data:file.write("".join(row)+'\n')#将地图数据用图片导出defexport_image(self,file_name="map.png")->None:cell_size=10image=Image.new("RGB",(self.width*cell_size,self.height*cell_size),"white")draw=ImageDraw.Draw(image)forxinrange(self.height):foryinrange(self.width):color="white"ifself.data[x][y]=="⬛":color="black"elifself.data[x][y]=="🟥":color="red"elifself.data[x][y]=="🟩":color="green"draw.rectangle([(y*cell_size,x*cell_size),((y+1)*cell_size,(x+1)*cell_size)],fill=color)image.save(file_name)#当地图点为⬛，则为障碍物defset_obstacle(self,x,y):self.data[x][y]="⬛"#设置起点和终点defset_start_end(self,startoint,endoint)->None:self.data[start.x][start.y]="🟥"self.data[end.x][end.y]="🟥"defobstacle_generate(self,ratio:int)->None:#随机放置障碍物obstacle_cells=int((self.height*self.width)*ratio)#障碍物占据40%的格子for_inrange(obstacle_cells):x=random.randint(0,map2d.height-1)y=random.randint(0,map2d.width-1)while(x==start_point.xandy==start_point.y)or(x==end_point.xandy==end_point.y)ormap2d.data[x][y]=="⬛":x=random.randint(0,map2d.height-1)y=random.randint(0,map2d.width-1)map2d.set_obstacle(x,y)"""1.ud指的是upanddown2.rl指的是rightandleft"""classNode:def__init__(self,pointoint,endpointoint,g:float):#初始化中间节点的参数self.point=pointself.endpoint=endpointself.father=Noneself.g=g#h取曼哈顿距离，c=|x2-x1|+|y2-y1|self.h=(abs(endpoint.x-point.x)+abs(endpoint.y-point.y))*10self.f=self.g+self.hdefget_near(self,ud,rl):#获取相邻节点near_point=Point(self.point.x+rl,self.point.y+ud)near_node=Node(near_point,self.endpoint,self.g+(10ifud==0orrl==0else14))returnnear_nodeclassAStar:def__init__(self,startoint,endoint,map2d:Map2D):#初始化A*算法的参数self.path=[]self.closed_list=[]self.open_list=[]self.start=startself.end=endself.map2d=map2d#从open_list里面找到一个代价最小的节点defselect_current(self)->Node:min_f=sys.maxsizenode_temp=Nonefornodeinself.open_list:ifnode.fbool:#判断节点是否在待检测队列中returnany([open_node.point==node.pointforopen_nodeinself.open_list])defis_in_closed_list(self,node:Node)->bool:#判断节点是否在已检测队列中returnany([closed_node.point==node.pointforclosed_nodeinself.closed_list])defis_obstacle(self,node:Node)->bool:#判断节点是否是障碍物returnself.map2d.data[node.point.x][node.point.y]=="⬛""""这个函数是A*算法的核心函数，找到当前节点代价最小的邻点用list来当作是队列的数据结构，存放探测过或者未被探测的节点，以此来进行路径探索在路径探索中节点有三种状态状态1.加入了队列并且已经检测了，这个单独用一个Close_list队列存放状态2.加入了队列但是还没有检测，这个用Open_list队列存放状态3.还没有被加入队列"""defexplore_neighbors(self,current_node:Node)->bool:up=(0,1)#上down=(0,-1)#下right=(1,0)#右left=(-1,0)#左top_right=(1,1)#右上top_left=(-1,1)#左上Bottom_right=(1,-1)#右下Bottom_left=(-1,-1)#左下directions=[up,down,right,left,top_right,top_left,Bottom_right,Bottom_left]fordirectionindirections:ud,rl=direction#current_neighbor是当前节点的邻点current_neighbor=current_node.get_near(ud,rl)#如果检测到的节点是终点，就没必要接着往下探索了，直接退出循环，结束这个函数ifcurrent_neighbor.point==self.end:returnTrue#判断一下邻点是不是已经检测或者是障碍物，如果是，就跳过这个邻点ifself.is_in_closed_list(current_neighbor)orself.is_obstacle(current_neighbor):continueifself.is_in_open_list(current_neighbor):"""作用:在open_list中找到第一个与current_neighbor相同(坐标相同)的节点这里有两个值得注意的点1.在open_list中,可能有多个与current_neighbor相同(坐标相同)的节点，出现这种情况是因为同一个节点，是可以通过多条不同的路径抵达的(意思就是g值不同)比如说节点C是当前节点,点A与节点B都能抵达节点C且g值都相同,那么节点C此时在open_list就会被添加两次2.previous_current_neighbor是取的在open_list中与current_neighbor相同(坐标相同)的节点中他们唯一的区别就是g值不同但因为有多个匹配,因此这里用next函数只取一次即可"""previous_current_neighbor=next(open_nodeforopen_nodeinself.open_listifopen_node.point==current_neighbor.point)"""这时就要比较current_neighbor与previous_current_neighbor的代价了,假如我在本次的路径探索到的current_neighbor要比我之前的路径探索到的previous_current_neighbor的代价要小(这里时刻注意,current_neighbor与previous_current_neighbor是坐标相同的),那么我就要更新previous_current_neighbor的代价"""ifcurrent_neighbor.f