A*算法(超级详细讲解,附有举例的详细手写步骤)-程序员宅基地

技术标签: 算法入门  算法  

背景:项目需要接触此算法,以下是一些自学成果,如有不足之处,欢迎指出,必虚心接受。做了一份PPT来汇报,此处直接使用自己PPT的截图。部分图片来源网络,如有侵权立马删除,以下博文仅作为学习笔记。后期又新增了完整PPT。

A*算法完整PTT_dujuancao11的博客-程序员宅基地

A*算法入门 - Jacc.Kim - 博客园

目录

A*寻路算法 

A*算法解决什么问题

A*算法的基本原理

A*算法的详细原理

A*算法的详细原理之定义

​A*算法的详细原理之初始设定 

​A*算法的详细原理之寻路原理

A*算法的详细原理之结束条件

A*算法的寻路详细步骤

A*算法的举例说明 

A*算法的伪代码

A*算法的定义伪代码 (C++)

A*算法的寻路伪代码(C++)

Python+PyQt代码实现

代码内容(可运行)

运行结果 

可执行文件

拓展

Dijkstra算法和A*算法的比较


A*寻路算法 

A*算法解决什么问题

A*算法的基本原理

A*算法的详细原理

A*算法的详细原理之定义

A*算法的详细原理之初始设定 

A*算法的详细原理之寻路原理

A*算法的详细原理之结束条件

 

A*算法的寻路详细步骤

S(start)起点              E(End)终点

A*算法的举例说明 

如果还不懂的话,可以参考我手写的计算步骤,再不懂可以私信我。(手稿字有点丑) 

 

A*算法的伪代码

A*算法的定义伪代码 (C++)

int open_list;//一个记录下所有被考虑来寻找最短路径的格子
int close_list; //一个记录下不会再被考虑的格子
typedef struct point{
	bool Is_Wall;
	struct point* father;//父节点
	int G;// 表示从起点 A 移动到网格上指定方格的移动耗费 (上下左右,还可沿斜方向移动)
	int old_G;//旧G 第一次:从起点 A 直接移动到 A 四周方格的移动耗费 ;上次更新得到的G 
	int new_G; //新G  从起点 A 经过当前搜索中心点到其四周指定点的移动耗费 
	int H;//表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动)
	int F=G+H;//表示该点的总耗费
}Point;
point* start_point;
point* end_point;
point* min_point; 
point* now_point; 

A*算法的寻路伪代码(C++)

//FindPath
do{
	//确定中心搜索点,上一个中心点关闭,新的中心点开启 
	查找:Find the minimumm "point" of "F" from the "open_list" center;
	"now_point" = "min_point";//minimumm point 
	"now_point"添加到"close_list";
	
	//新中心点的周围点开启,新中心点关闭 
	循环遍历:"now_point"相邻的周围8格"s_now_point"中的每一个;
	//这一块它指的就是now_point周围8点当前搜索点 s_now_point,为了简单直接用它表示 
	if (它不可通过||它已经在"close_list"中){
		什么也不做;
	} else if (它不在开启列表中){
		把它添加进"open_list";
		把"now_point"作为这它的"father",计算它的"F","G","H";
	}else if (它已经在开启列表中){//通过G来判断是否需要更新 
		if (new_G < old_G){
			更新它的"father"为当前中心搜索点"now_point";
			更新它的"G"与"F" ;
		} else{
			不更新,保持原来的"father", "G"与"F" ;
		} 
	}
} while(目标格"end_point"已经在"open_list"||"open_list"==NULL)
//存在路径:目标格"end_point"已经在"open_list"
//不存在路径: "open_list"==NULL,搜索了所有可能的点 

Python+PyQt代码实现

代码内容(可运行)

import time,sys
from PyQt5.QtWidgets import QDialogButtonBox,QDialog,QMainWindow,QGridLayout,QTextEdit,QLineEdit,QWidget, QMessageBox, QApplication,QLabel,QPushButton,QHBoxLayout,QVBoxLayout
from PyQt5.QtCore import Qt,QTimer,QObject,pyqtSignal,QBasicTimer
from PyQt5.QtGui import QPainter, QColor, QFont,QPen
import json
class config:
	WIDTH=20#地图列数
	HEIGHT=20#地图行数
	blockLength=30#绘制画面时每一个节点方块的边长
class point:#点类(每一个唯一坐标只有对应的一个实例)
	_list=[]#储存所有的point类实例
	_tag=True#标记最新创建的实例是否为_list中的已有的实例,True表示不是已有实例
	def __new__(cls,x,y):#重写new方法实现对于同样的坐标只有唯一的一个实例
		for i in point._list:
			if i.x==x and i.y==y:
				point._tag=False
				return i
		nt=super(point,cls).__new__(cls)
		point._list.append(nt)
		return nt
	def __init__(self,x,y):
		if point._tag:
			self.x=x
			self.y=y
			self.father=None
			self.F=0#当前点的评分  F=G+H
			self.G=0#起点到当前节点所花费的消耗
			self.cost=0#父节点到此节点的消耗
		else:
			point._tag=True
	@classmethod
	def clear(cls):#clear方法,每次搜索结束后,将所有点数据清除,以便进行下一次搜索的时候点数据不会冲突。
		point._list=[]
	def __eq__(self,T):#重写==运算以便实现point类的in运算
		if type(self)==type(T):
			return (self.x,self.y)==(T.x,T.y)
		else:
			return False
	def __str__(self):
		return'(%d,%d)[F=%d,G=%d,cost=%d][father:(%s)]'%(self.x,self.y,self.F,self.G,self.cost,str((self.father.x,self.father.y)) if self.father!=None else 'null')
class A_Search:#核心部分,寻路类
	def __init__(self,arg_start,arg_end,arg_map):
		self.start=arg_start#储存此次搜索的开始点
		self.end=arg_end#储存此次搜索的目的点
		self.Map=arg_map#一个二维数组,为此次搜索的地图引用
		self.open=[]#开放列表:储存即将被搜索的节点
		self.close=[]#关闭列表:储存已经搜索过的节点
		self.result=[]#当计算完成后,将最终得到的路径写入到此属性中
		self.count=0#记录此次搜索所搜索过的节点数
		self.useTime=0#记录此次搜索花费的时间--在此演示中无意义,因为process方法变成了一个逐步处理的生成器,统计时间无意义。
		#开始进行初始数据处理
		self.open.append(arg_start)
	def cal_F(self,loc):
		print('计算值:',loc)
		G=loc.father.G+loc.cost
		H=self.getEstimate(loc)
		F=G+H
		print("F=%d G=%d H=%d"%(F,G,H))
		return {'G':G,'H':H,'F':F}
	def F_Min(self):#搜索open列表中F值最小的点并将其返回,同时判断open列表是否为空,为空则代表搜索失败
		if len(self.open)<=0:
			return None
		t=self.open[0]
		for i in self.open:
			if i.F<t.F:
				t=i
		return t
	def getAroundPoint(self,loc):#获取指定点周围所有可通行的点,并将其对应的移动消耗进行赋值。
		l=[(loc.x,loc.y+1,10),(loc.x+1,loc.y+1,14),(loc.x+1,loc.y,10),(loc.x+1,loc.y-1,14),(loc.x,loc.y-1,10),(loc.x-1,loc.y-1,14),(loc.x-1,loc.y,10),(loc.x-1,loc.y+1,14)]
		for i in l[::-1]:
			if i[0]<0 or i[0]>=config.HEIGHT or i[1]<0 or i[1]>=config.WIDTH:
				l.remove(i)
		nl=[]
		for i in l:
			if self.Map[i[0]][i[1]]==0:
				nt=point(i[0],i[1])
				nt.cost=i[2]
				nl.append(nt)
		return nl

	def addToOpen(self,l,father):#此次判断的点周围的可通行点加入到open列表中,如此点已经在open列表中则对其进行判断,如果此次路径得到的F值较之之前的F值更小,则将其父节点更新为此次判断的点,同时更新F、G值。
		for i in l:
			if i not in self.open:
				if i not in self.close:
					i.father=father
					self.open.append(i)
					r=self.cal_F(i)
					i.G=r['G']
					i.F=r['F']
			else:
				tf=i.father
				i.father=father
				r=self.cal_F(i)
				if i.F>r['F']:
					i.G=r['G']
					i.F=r['F']
					# i.father=father
				else:
					i.father=tf
	def getEstimate(self,loc):#H :从点loc移动到终点的预估花费
		return (abs(loc.x-self.end.x)+abs(loc.y-self.end.y))*10
	def DisplayPath(self):#在此演示中无意义
		print('搜索花费的时间:%.2fs.迭代次数%d,路径长度:%d'%(self.useTime,self.count,len(self.result)))
		if self.result!=None:
			for i in self.result:
				self.Map[i.x][i.y]=8
			for i in self.Map:
				for j in i:
					if j==0:
						print('%s'%'□',end='')
					elif j==1:
						print('%s'%'▽',end='')
					elif j==8:
						print('%s'%'★',end='')
				print('')
		else:
			print('搜索失败,无可通行路径')
	def process(self):#使用yield将process方法变成一个生成器,可以逐步的对搜索过程进行处理并返回关键数据
		while True:
			self.count+=1
			tar=self.F_Min()#先获取open列表中F值最低的点tar
			if tar==None:
				self.result=None
				self.count=-1
				break
			else:
				aroundP=self.getAroundPoint(tar)#获取tar周围的可用点列表aroundP
				self.addToOpen(aroundP,tar)#把aroundP加入到open列表中并更新F值以及设定父节点
				self.open.remove(tar)#将tar从open列表中移除
				self.close.append(tar)#已经迭代过的节点tar放入close列表中
				if self.end in self.open:#判断终点是否已经处于open列表中
					e=self.end
					self.result.append(e)
					while True:
						e=e.father
						if e==None:
							break
						self.result.append(e)
					yield (tar,self.open,self.close)
					break

			# self.repaint()
			# print('返回')
			yield (tar,self.open,self.close)
			time.sleep(5)#暂停
		self.useTime=time2-time1
class GameBoard(QMainWindow):#可视化类,pyqt5进行编写。
	def __init__(self):
		print('初始化地图...')
		self.Map=[]
		for i in range(config.HEIGHT):
			col=[]
			for j in range(config.WIDTH):
				col.append(0)
			self.Map.append(col)
		self.startPoint=None
		self.endPoint=None
		self.search=None
		self.centerTimer=None
		self.yi=None
		self.special=None
		self.displayFlush=False
		super().__init__()
		print('初始化UI...')
		self.initUI()
	def initUI(self):
		#开始初始化UI部分
			#创建UI控件
		self.label_tips=QLabel("<p style='color:green'>使用说明:</p>右键单击格子选定起始点,左键格子选定格子为墙壁或删除墙壁。\n<p style='color:green'>颜色说明:</p>\n黄色代表起点,绿色代表终点,黑色代表墙壁,红色代表待搜索的open列表,灰色代表已搜索过的close列表,蓝色代表当前搜索到的路径",self)
		self.label_display=QLabel("",self)
		self.button_start=QPushButton("开始搜索",self)
		self.button_clearSE=QPushButton("重选起始点",self)
		self.button_clearWall=QPushButton("清空地图墙壁",self)
		self.button_saveMap=QPushButton("保存地图",self)
		self.button_loadMap=QPushButton("加载地图",self)


			#设置控件属性
		self.label_tips.setWordWrap(True)
		self.label_display.setWordWrap(True)
			#设置控件样式
		self.label_display.setStyleSheet("border:1px solid black")
		self.label_display.setAlignment(Qt.AlignLeft)
		self.label_display.setAlignment(Qt.AlignTop)
			#设置控件的尺寸和位置
		self.label_tips.resize(200,150)
		self.button_saveMap.resize(80,30)
		self.button_loadMap.resize(80,30)
		self.label_display.resize(200,300)

		self.label_tips.move(100+(config.WIDTH-1)*config.blockLength,0)
		self.label_display.move(100+(config.WIDTH-1)*config.blockLength,400)
		self.button_start.move(100+(config.WIDTH-1)*config.blockLength,200)
		self.button_clearSE.move(100+(config.WIDTH-1)*config.blockLength,250)
		self.button_clearWall.move(100+(config.WIDTH-1)*config.blockLength,300)
		self.button_saveMap.move(100+(config.WIDTH-1)*config.blockLength,350)
		self.button_loadMap.move(200+(config.WIDTH-1)*config.blockLength,350)
			#给控件绑定事件
		self.button_start.clicked.connect(self.button_StartEvent)
		self.button_clearSE.clicked.connect(self.button_Clear)
		self.button_clearWall.clicked.connect(self.button_Clear)
		self.button_saveMap.clicked.connect(self.button_SaveMap)
		self.button_loadMap.clicked.connect(self.button_LoadMap)
		#UI初始化完成
		self.setGeometry(0, 0, 150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
		self.setMinimumSize(150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
		self.setMaximumSize(150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
		self.setWindowTitle('A*搜索')
		self.show()
	def addDisplayText(self,text):
		if self.displayFlush:
			self.label_display.setText(text+'\n')
			self.displayFlush=False
		else:
			self.label_display.setText(self.label_display.text()+text+'\n')
	def mousePressEvent(self,event):
		x,y=event.x()-50,event.y()-50
		x=x//config.blockLength
		y=y//config.blockLength
		if x>=0 and x<config.WIDTH and y>=0 and y<config.HEIGHT:
			if event.button()==Qt.LeftButton:
				if (x,y)!=self.startPoint and (x,y)!=self.endPoint:
					self.Map[y][x]=(1 if self.Map[y][x]==0 else 0)
			if event.button()==Qt.RightButton:
				if self.Map[y][x]==0:
					if self.startPoint==None:
						self.startPoint=(x,y)
						self.addDisplayText('添加了一个起点:(%d,%d)'%(x,y))
					elif self.endPoint==None and self.startPoint!=(x,y):
						self.endPoint=(x,y)
						self.addDisplayText('添加了一个终点:(%d,%d)'%(x,y))
			self.repaint()
	def button_StartEvent(self):
		sender=self.sender()
		print(sender)
		if self.startPoint!=None and self.endPoint!=None:
			if self.centerTimer==None:
				self.centerTimer=QBasicTimer()
			self.button_start.setEnabled(False)
			self.button_clearSE.setEnabled(False)
			self.button_clearWall.setEnabled(False)
			self.centerTimer.start(200,self)
			self.search=A_Search(point(self.startPoint[1],self.startPoint[0]),point(self.endPoint[1],self.endPoint[0]),self.Map)
			self.yi=self.search.process()
			self.addDisplayText('开始进行搜索')
	def button_SaveMap(self):
		with open('map.txt','w') as f:
			f.write(json.dumps(self.Map))
			self.addDisplayText('地图保存成功-->map.txt')
		# else:
			# self.addDisplayText('地图保存失败')
	def button_LoadMap(self):
		try:
			with open('map.txt','r') as f:
				self.Map=json.loads(f.read())
				config.HEIGHT=len(self.Map)
				config.WIDTH=len(self.Map[0])
				self.addDisplayText('地图加载成功')
				self.repaint()
		except Exception as e:
			print('失败',e,type(e))
			if type(e)==FileNotFoundError:
				self.addDisplayText('地图加载失败:地图文件不存在')
			elif type(e)==json.decoder.JSONDecodeError:
				self.addDisplayText('地图加载失败:错误的地图文件')
	def button_Clear(self):
		sender=self.sender()
		print(self.button_clearSE,type(self.button_clearSE))
		if sender==self.button_clearSE:
			self.startPoint=None
			self.endPoint=None
			self.repaint()
			self.addDisplayText('清空起始点')
		elif sender==self.button_clearWall:
			for i in range(len(self.Map)):
				for j in range(len(self.Map[i])):
					self.Map[i][j]=0
			self.repaint()
			self.addDisplayText('清空所有墙壁')
	def paintEvent(self, event):
		qp = QPainter()
		qp.begin(self)
		self.drawBoard(event,qp)
		qp.end()
	def drawBoard(self, event, qp):
	    self.drawMap(qp)
	def drawMap(self,qp):#画面绘制方法,每次地图有所改动都将重绘
		time1=time.time()
		if self.search!=None:
			if self.special!=None:
				e=self.special[0]
				path=[e]
				while True:
					e=e.father
					if e!=None:
						path.append(e)
					else:
						break
			else:
				path=None
			pen=QPen(QColor(0,0,0),1,Qt.SolidLine)
			qp.setPen(pen)
			for i in range(len(self.Map)):
				for j in range(len(self.Map[i])):
					wordTag=False
					if i==self.search.start.x and j==self.search.start.y:
						qp.setBrush(QColor(255,255,0))
					elif i==self.search.end.x and j==self.search.end.y:
						qp.setBrush(QColor(100,200,50))
					else:
						if self.Map[i][j]==0:
							tagx=True
							if path:
								for k in path:
									if k.x==i and k.y==j:
										tagx=False
										qp.setBrush(QColor(0,100,255))
							if tagx:
								if self.special!=None:
									if i==self.special[0].x and j==self.special[0].y:
										qp.setBrush(QColor(0,255,0))
									else:
										tag=True
										for k in self.special[1]:
											if k.x==i and k.y==j:
												tag=False
												wordTag=True
												word=str(k.F)

												qp.setBrush(QColor(150,0,0))
												break
											else:
												qp.setBrush(QColor(220,220,220))
										if tag:
											for k in self.special[2]:
												if k.x==i and k.y==j:
													qp.setBrush(QColor(150,150,150))
													break
												else:
													qp.setBrush(QColor(220,220,220))
								else:
									qp.setBrush(QColor(220,220,220))
						elif self.Map[i][j]==1:
							qp.setBrush(QColor(0,0,0))
						else:
							qp.setBrush(QColor(255,0,0))
					qp.drawRect(50+j*config.blockLength,50+i*config.blockLength,config.blockLength,config.blockLength)
					if wordTag:
						qp.setFont(QFont('楷体',5,QFont.Light))
						qp.drawText(50+10+j*config.blockLength,50+10+i*config.blockLength,word)
						wordTag=False
		#time.sleep(20)
		else:
			for i in range(len(self.Map)):
				for j in range(len(self.Map[i])):
					if (j,i)==self.startPoint:
						qp.setBrush(QColor(255,255,0))
					elif (j,i)==self.endPoint:
						qp.setBrush(QColor(100,200,50))
					else:
						if self.Map[i][j]==0:
							qp.setBrush(QColor(220,220,220))
						elif self.Map[i][j]==1:
							qp.setBrush(QColor(0,0,0))
						else:
							qp.setBrush(QColor(255,0,0))

					qp.drawRect(50+j*config.blockLength,50+i*config.blockLength,config.blockLength,config.blockLength)
		time2=time.time()
	#time.sleep(20)
		# print('绘制时间:',time2-time1)
	def timerEvent(self,e):
		try:
			data=next(self.yi)
		except Exception as e:
			self.addDisplayText('搜索结束:')
			print('搜索结束!')
			if self.search.result==None:
				self.addDisplayText('未找到可行路径')
				print('搜索结束!')
			else:
				self.addDisplayText('总计搜索节点数:%d'%self.search.count)
				self.addDisplayText('最终路径长度:%d'%len(self.search.result))
			self.centerTimer.stop()
			self.search=None
			self.yi=None
			self.special=None
			point.clear()
			self.button_start.setEnabled(True)
			self.button_clearSE.setEnabled(True)
			self.button_clearWall.setEnabled(True)
			self.displayFlush=True
		else:
			self.special=data
			self.repaint()
if __name__ == '__main__':
	app = QApplication(sys.argv)
	ex = GameBoard()
	sys.exit(app.exec_())

注意:代码运行可以设置动态遍历的时候暂停时间(大概在145行的time.sleep(5)语句)

运行结果 

输出每次计算的每个点的F和父结点,直接看图吧!

详细列表

初始化地图...
初始化UI...
<PyQt5.QtWidgets.QPushButton object at 0x0000017CC699AC18>
计算值: (2,3)[F=0,G=0,cost=10][father:((2, 2))]
F=40 G=10 H=30
计算值: (3,3)[F=0,G=0,cost=14][father:((2, 2))]
F=54 G=14 H=40
计算值: (3,2)[F=0,G=0,cost=10][father:((2, 2))]
F=60 G=10 H=50
计算值: (3,1)[F=0,G=0,cost=14][father:((2, 2))]
F=74 G=14 H=60
计算值: (2,1)[F=0,G=0,cost=10][father:((2, 2))]
F=60 G=10 H=50
计算值: (1,1)[F=0,G=0,cost=14][father:((2, 2))]
F=74 G=14 H=60
计算值: (1,2)[F=0,G=0,cost=10][father:((2, 2))]
F=60 G=10 H=50
计算值: (1,3)[F=0,G=0,cost=14][father:((2, 2))]
F=54 G=14 H=40
计算值: (3,3)[F=54,G=14,cost=10][father:((2, 3))]
F=60 G=20 H=40
计算值: (3,2)[F=60,G=10,cost=14][father:((2, 3))]
F=74 G=24 H=50
计算值: (1,2)[F=60,G=10,cost=14][father:((2, 3))]
F=74 G=24 H=50
计算值: (1,3)[F=54,G=14,cost=10][father:((2, 3))]
F=60 G=20 H=40
计算值: (4,4)[F=0,G=0,cost=14][father:((3, 3))]
F=68 G=28 H=40
计算值: (4,3)[F=0,G=0,cost=10][father:((3, 3))]
F=74 G=24 H=50
计算值: (4,2)[F=0,G=0,cost=14][father:((3, 3))]
F=88 G=28 H=60
计算值: (3,2)[F=60,G=10,cost=10][father:((3, 3))]
F=74 G=24 H=50
计算值: (1,2)[F=60,G=10,cost=10][father:((1, 3))]
F=74 G=24 H=50
计算值: (0,2)[F=0,G=0,cost=14][father:((1, 3))]
F=88 G=28 H=60
计算值: (0,3)[F=0,G=0,cost=10][father:((1, 3))]
F=74 G=24 H=50
计算值: (0,4)[F=0,G=0,cost=14][father:((1, 3))]
F=68 G=28 H=40
计算值: (4,3)[F=74,G=24,cost=14][father:((3, 2))]
F=74 G=24 H=50
计算值: (4,2)[F=88,G=28,cost=10][father:((3, 2))]
F=80 G=20 H=60
计算值: (4,1)[F=0,G=0,cost=14][father:((3, 2))]
F=94 G=24 H=70
计算值: (3,1)[F=74,G=14,cost=10][father:((3, 2))]
F=80 G=20 H=60
计算值: (2,1)[F=60,G=10,cost=14][father:((3, 2))]
F=74 G=24 H=50
计算值: (3,1)[F=74,G=14,cost=10][father:((2, 1))]
F=80 G=20 H=60
计算值: (3,0)[F=0,G=0,cost=14][father:((2, 1))]
F=94 G=24 H=70
计算值: (2,0)[F=0,G=0,cost=10][father:((2, 1))]
F=80 G=20 H=60
计算值: (1,0)[F=0,G=0,cost=14][father:((2, 1))]
F=94 G=24 H=70
计算值: (1,1)[F=74,G=14,cost=10][father:((2, 1))]
F=80 G=20 H=60
计算值: (1,2)[F=60,G=10,cost=14][father:((2, 1))]
F=74 G=24 H=50
计算值: (1,1)[F=74,G=14,cost=10][father:((1, 2))]
F=80 G=20 H=60
计算值: (0,1)[F=0,G=0,cost=14][father:((1, 2))]
F=94 G=24 H=70
计算值: (0,2)[F=88,G=28,cost=10][father:((1, 2))]
F=80 G=20 H=60
计算值: (0,3)[F=74,G=24,cost=14][father:((1, 2))]
F=74 G=24 H=50
计算值: (4,5)[F=0,G=0,cost=10][father:((4, 4))]
F=68 G=38 H=30
计算值: (5,5)[F=0,G=0,cost=14][father:((4, 4))]
F=82 G=42 H=40
计算值: (5,4)[F=0,G=0,cost=10][father:((4, 4))]
F=88 G=38 H=50
计算值: (5,3)[F=0,G=0,cost=14][father:((4, 4))]
F=102 G=42 H=60
计算值: (4,3)[F=74,G=24,cost=10][father:((4, 4))]
F=88 G=38 H=50
计算值: (3,5)[F=0,G=0,cost=14][father:((4, 4))]
F=62 G=42 H=20
计算值: (3,6)[F=0,G=0,cost=10][father:((3, 5))]
F=62 G=52 H=10
计算值: (4,6)[F=0,G=0,cost=14][father:((3, 5))]
F=76 G=56 H=20
计算值: (4,5)[F=68,G=38,cost=10][father:((3, 5))]
F=82 G=52 H=30
计算值: (2,5)[F=0,G=0,cost=10][father:((3, 5))]
F=62 G=52 H=10
计算值: (2,6)[F=0,G=0,cost=14][father:((3, 5))]
F=56 G=56 H=0
搜索结束!

可执行文件

已经将程序打包成exe可执行文件,点击即可用,不需要py环境。

链接:https://pan.baidu.com/s/1UqvI5vtoxwXu0PPUFHfxdg 
提取码:fwwm 
复制这段内容后打开百度网盘手机App,操作更方便哦

拓展

Dijkstra算法和A*算法的比较

Dijkstra算法和A*都是最短路径问题的常用算法,下面就对这两种算法的特点进行一下比较。
1.Dijkstra算法计算源点到其他所有点的最短路径长度,A*关注点到点的最短路径(包括具体路径)。
2.Dijkstra算法建立在较为抽象的图论层面,A*算法可以更轻松地用在诸如游戏地图寻路中。
3.Dijkstra算法的实质是广度优先搜索,是一种发散式的搜索,所以空间复杂度和时间复杂度都比较高。对路径上的当前点,A*算法不但记录其到源点的代价,还计算当前点到目标点的期望代价,是一种启发式算法,也可以认为是一种深度优先的算法。
4.由第一点,当目标点很多时,A*算法会带入大量重复数据和复杂的估价函数,所以如果不要求获得具体路径而只比较路径长度时,Dijkstra算法会成为更好的选择。

参考:https://blog.csdn.net/weixin_42382758/article/details/88840581

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dujuancao11/article/details/109749219

智能推荐

ue4 植被部分消失或全部消失问题_ue渲染植物消失-程序员宅基地

文章浏览阅读1.7w次。有的时候录制全景的时候发现部分植被消失了现在确认这个是ue4的已知bug造成的结果如上图,是ue4上一种靠反射球生成全景的插件结果,可以看到地面上植被消失,只留下植被的阴影貌似超过1.5k的植被(foliage形式)就会在全景上消失消失的植物是超过1.5k的那一种这个问题也会出现在反射相关的材质中 具体问题如下https://issues.unrealengin..._ue渲染植物消失

Elasticsearch:keyword类型和text类型的区别-程序员宅基地

文章浏览阅读1.5k次。text比keyword多出了分词处理,所以从内存占比与性能上来看,如果keyword满足业务场景并且业务场景中不需要分词,那么优先使用keyword,因为其内存占比更低,性能更优。

list转Array-程序员宅基地

文章浏览阅读6.5k次。集合转数组必须使用集合的 toArray(T[] array),传入的是类型完全一样的数组,大小就是 list.size()。说明:使用 toArray 带参方法,入参分配的数组空间不够大时,toArray 方法内部将重新分配内存空间,并返回新数组地址;如果数组元素大于实际所需,下标为[ list.size() ]的数组元素将被置为 null,其它数组元素保持原值,因此最好将方法入参组大小定义与集合元素个数一致。正例:List<String> list = new ArrayLi_list转array

关于jsp页面报属性“”的值为 null、未定义或不是 Function 对象的错误_属性值为null未定义或不为function对象-程序员宅基地

文章浏览阅读7.4k次。**今天写代码遇到的问题,以前也遇到过,但是没重视,今天特地花时间来解决来一下。** 如果遇到这个问题,绝大多数原因是和jsp页面掺杂的java代码片段有关,记住,当用&amp;lt;%=值 %&amp;gt; 来和字符串类型变量做比较运算时,**要在&amp;lt;%=值 %&amp;gt;外面加一层双引号**,否则就会报这个错误。如果遇到的问题不是这个类型,就需要仔细查找代码有没有遗漏细节,比如引号分号逗号括号之..._属性值为null未定义或不为function对象

分析总结常见的几种移动机器人底盘类型及其运动学_机器人比赛前驱还是后驱-程序员宅基地

文章浏览阅读2.9w次,点赞43次,收藏374次。前言(Preface)最近想做一个关于移动机器人的总结,就先从移动机器人的底盘说起吧。现在移动机器人这么火热,大到无人驾驶车,规矩的有工业上应用得很多的AGV(比如智能物流自动搬运机器人),小到淘宝上面的智能小车,都可以算作移动机器人。移动机器人有各种各样的底盘,有两轮的三轮的四轮的,比如无人车是四轮的阿克曼模型,一般的AGV是两轮差速模型,还有大学生机器人竞赛里面常见的三轮全向轮底盘,四轮全..._机器人比赛前驱还是后驱

python连接redis,错误redis.exceptions.ConnectionError: Error 10061 connecting to XXXX. 由于目标计_python 连接windows redis 报redis.exceptions.connectio-程序员宅基地

文章浏览阅读3.5k次。这里写自定义目录标题总结本人主机使用python连接Ubuntu(虚拟机)上的redis的一个坑(挺蠢的)我是在本机上使用python去连接虚拟机中的ubuntu中的redis中的问题解决方法如下,首先确认redis服务是否开启打开任务管理器->服务,找到是否有Redis没有的话就去下载一个就好了,有很多其他文章都有描述,我就不再描述了在ubuntu中,首先确认防火墙的状态,我只使用了ufw防火墙,当然如果你开启了防火墙出现的错误代码也就不一样了——————————————————_python 连接windows redis 报redis.exceptions.connectionerror: error 10061 con

随便推点

应用市场大全-程序员宅基地

文章浏览阅读189次。2019独角兽企业重金招聘Python工程师标准>>> ..._各应用市场信息大全

JMeter安装配置教程_linux error: unable to access jarfile /data/apache-程序员宅基地

文章浏览阅读6.9k次,点赞9次,收藏26次。JMeter安装配置教程1.安装JDK和JRE2.点击进入Apache JMeter 官网下载安装包点击下载Binaries中的apache-jmeter-5.4.1.zip;如果下载Source里面的apache-jmeter-5.4.1_src.zip会报下面的错误:Error: Unable to access jarfile ApacheJMeter.jar errorlevel=13.解压apache-jmeter-5.4.1.zip文件至D:\software目录下;4.我的_linux error: unable to access jarfile /data/apache-jmeter-5.4.1/bin/apachejm

【响应式Web设计】读书笔记 - 弹性布局与响应式图片(一) - 3_通过弹性布局实现一个响应式导航菜单,即导航菜单随屏幕大小的变化而变化。当鼠标-程序员宅基地

文章浏览阅读836次。【简介】一开始设计网页的时候,网站的宽度都以百分比形式定义。百分比布局使得网页宽度能够随着查看它们的屏幕窗口大小变化,即弹性布局。后来,又回到了固定宽度设计的风潮,因为固定宽度可以有「像素级精度设计」的网页。现如今,而为了能够做好固定宽度在不同屏幕中的自适应,出现了响应式设计。_通过弹性布局实现一个响应式导航菜单,即导航菜单随屏幕大小的变化而变化。当鼠标

基于ENVI下的土地利用信息提取(三)_envi提取dem影像的经纬度数据-程序员宅基地

文章浏览阅读1.7w次,点赞12次,收藏106次。5.4 DEM数据的获取与预处理DEM高程数据用栅格像元值的方式来存储地表的高程信息,我国目前以黄海的平均海水面为高程基准,图像中的每个栅格值代表该位置与黄海水平面的相对高度,即海拔高度。在网上免费下载的DEM高程数据的空间参考为记录经纬度的地理坐标系,基准面为WGS_1984,其分辨率为90m,这与所给的研究区的TM影像的空间参考和分辨率无法匹配,故下面需要对下载的DEM数据进行投影_envi提取dem影像的经纬度数据

【windows】win10 系统设置 cmd 中常用命令的别名(alias)_windiows path 命令别名-程序员宅基地

文章浏览阅读2.1k次。新建bat文件在某个目录下(建议在用户根目录)新建文件cmd_auto.bat , 输入自己需要的常用命令的别名。下面是我的cmd_auto.bat:@echo offdoskey ls=dir /b $*doskey act=activate tensorflow-gpu $*doskey tb=tensorboard --logdir $*doskey pi=pip install $*doskey nb=jupyter notebook $*说明:doskey相当于Linu._windiows path 命令别名

2022将至,前端程序员们应该一起放个烟花庆祝一下,走起-程序员宅基地

文章浏览阅读7.1k次,点赞26次,收藏10次。使用html实现自定义烟花效果,人人都可以操作一把~