devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

A*算法（超级详细讲解，附有举例的详细手写步骤）

作者：不正经 | 2024-03-10 21:14:32

赞

踩

a*算法

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

目录

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++)

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

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

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

Python+PyQt代码实现

代码内容（可运行）

  1. import time,sys
  2. from PyQt5.QtWidgets import QDialogButtonBox,QDialog,QMainWindow,QGridLayout,QTextEdit,QLineEdit,QWidget, QMessageBox, QApplication,QLabel,QPushButton,QHBoxLayout,QVBoxLayout
  3. from PyQt5.QtCore import Qt,QTimer,QObject,pyqtSignal,QBasicTimer
  4. from PyQt5.QtGui import QPainter, QColor, QFont,QPen
  5. import json
  6. class config:
  7. 	WIDTH=20#地图列数
  8. 	HEIGHT=20#地图行数
  9. 	blockLength=30#绘制画面时每一个节点方块的边长
  10. class point:#点类（每一个唯一坐标只有对应的一个实例）
  11. 	_list=[]#储存所有的point类实例
  12. 	_tag=True#标记最新创建的实例是否为_list中的已有的实例，True表示不是已有实例
  13. 	def __new__(cls,x,y):#重写new方法实现对于同样的坐标只有唯一的一个实例
  14. 		for i in point._list:
  15. 			if i.x==x and i.y==y:
  16. 				point._tag=False
  17. 				return i
  18. 		nt=super(point,cls).__new__(cls)
  19. 		point._list.append(nt)
  20. 		return nt
  21. 	def __init__(self,x,y):
  22. 		if point._tag:
  23. 			self.x=x
  24. 			self.y=y
  25. 			self.father=None
  26. 			self.F=0#当前点的评分  F=G+H
  27. 			self.G=0#起点到当前节点所花费的消耗
  28. 			self.cost=0#父节点到此节点的消耗
  29. 		else:
  30. 			point._tag=True
  31. 	@classmethod
  32. 	def clear(cls):#clear方法，每次搜索结束后，将所有点数据清除，以便进行下一次搜索的时候点数据不会冲突。
  33. 		point._list=[]
  34. 	def __eq__(self,T):#重写==运算以便实现point类的in运算
  35. 		if type(self)==type(T):
  36. 			return (self.x,self.y)==(T.x,T.y)
  37. 		else:
  38. 			return False
  39. 	def __str__(self):
  40. 		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')
  41. class A_Search:#核心部分，寻路类
  42. 	def __init__(self,arg_start,arg_end,arg_map):
  43. 		self.start=arg_start#储存此次搜索的开始点
  44. 		self.end=arg_end#储存此次搜索的目的点
  45. 		self.Map=arg_map#一个二维数组，为此次搜索的地图引用
  46. 		self.open=[]#开放列表：储存即将被搜索的节点
  47. 		self.close=[]#关闭列表：储存已经搜索过的节点
  48. 		self.result=[]#当计算完成后，将最终得到的路径写入到此属性中
  49. 		self.count=0#记录此次搜索所搜索过的节点数
  50. 		self.useTime=0#记录此次搜索花费的时间--在此演示中无意义，因为process方法变成了一个逐步处理的生成器，统计时间无意义。
  51. 		#开始进行初始数据处理
  52. 		self.open.append(arg_start)
  53. 	def cal_F(self,loc):
  54. 		print('计算值：',loc)
  55. 		G=loc.father.G+loc.cost
  56. 		H=self.getEstimate(loc)
  57. 		F=G+H
  58. 		print("F=%d G=%d H=%d"%(F,G,H))
  59. 		return {'G':G,'H':H,'F':F}
  60. 	def F_Min(self):#搜索open列表中F值最小的点并将其返回，同时判断open列表是否为空，为空则代表搜索失败
  61. 		if len(self.open)<=0:
  62. 			return None
  63. 		t=self.open[0]
  64. 		for i in self.open:
  65. 			if i.F<t.F:
  66. 				t=i
  67. 		return t
  68. 	def getAroundPoint(self,loc):#获取指定点周围所有可通行的点，并将其对应的移动消耗进行赋值。
  69. 		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)]
  70. 		for i in l[::-1]:
  71. 			if i[0]<0 or i[0]>=config.HEIGHT or i[1]<0 or i[1]>=config.WIDTH:
  72. 				l.remove(i)
  73. 		nl=[]
  74. 		for i in l:
  75. 			if self.Map[i[0]][i[1]]==0:
  76. 				nt=point(i[0],i[1])
  77. 				nt.cost=i[2]
  78. 				nl.append(nt)
  79. 		return nl
  80.  
  81. 	def addToOpen(self,l,father):#此次判断的点周围的可通行点加入到open列表中，如此点已经在open列表中则对其进行判断，如果此次路径得到的F值较之之前的F值更小，则将其父节点更新为此次判断的点，同时更新F、G值。
  82. 		for i in l:
  83. 			if i not in self.open:
  84. 				if i not in self.close:
  85. 					i.father=father
  86. 					self.open.append(i)
  87. 					r=self.cal_F(i)
  88. 					i.G=r['G']
  89. 					i.F=r['F']
  90. 			else:
  91. 				tf=i.father
  92. 				i.father=father
  93. 				r=self.cal_F(i)
  94. 				if i.F>r['F']:
  95. 					i.G=r['G']
  96. 					i.F=r['F']
  97. 					# i.father=father
  98. 				else:
  99. 					i.father=tf
  100. 	def getEstimate(self,loc):#H :从点loc移动到终点的预估花费
  101. 		return (abs(loc.x-self.end.x)+abs(loc.y-self.end.y))*10
  102. 	def DisplayPath(self):#在此演示中无意义
  103. 		print('搜索花费的时间:%.2fs.迭代次数%d,路径长度:%d'%(self.useTime,self.count,len(self.result)))
  104. 		if self.result!=None:
  105. 			for i in self.result:
  106. 				self.Map[i.x][i.y]=8
  107. 			for i in self.Map:
  108. 				for j in i:
  109. 					if j==0:
  110. 						print('%s'%'□',end='')
  111. 					elif j==1:
  112. 						print('%s'%'▽',end='')
  113. 					elif j==8:
  114. 						print('%s'%'★',end='')
  115. 				print('')
  116. 		else:
  117. 			print('搜索失败，无可通行路径')
  118. 	def process(self):#使用yield将process方法变成一个生成器，可以逐步的对搜索过程进行处理并返回关键数据
  119. 		while True:
  120. 			self.count+=1
  121. 			tar=self.F_Min()#先获取open列表中F值最低的点tar
  122. 			if tar==None:
  123. 				self.result=None
  124. 				self.count=-1
  125. 				break
  126. 			else:
  127. 				aroundP=self.getAroundPoint(tar)#获取tar周围的可用点列表aroundP
  128. 				self.addToOpen(aroundP,tar)#把aroundP加入到open列表中并更新F值以及设定父节点
  129. 				self.open.remove(tar)#将tar从open列表中移除
  130. 				self.close.append(tar)#已经迭代过的节点tar放入close列表中
  131. 				if self.end in self.open:#判断终点是否已经处于open列表中
  132. 					e=self.end
  133. 					self.result.append(e)
  134. 					while True:
  135. 						e=e.father
  136. 						if e==None:
  137. 							break
  138. 						self.result.append(e)
  139. 					yield (tar,self.open,self.close)
  140. 					break
  141.  
  142. 			# self.repaint()
  143. 			# print('返回')
  144. 			yield (tar,self.open,self.close)
  145. 			time.sleep(5)#暂停
  146. 		self.useTime=time2-time1
  147. class GameBoard(QMainWindow):#可视化类，pyqt5进行编写。
  148. 	def __init__(self):
  149. 		print('初始化地图...')
  150. 		self.Map=[]
  151. 		for i in range(config.HEIGHT):
  152. 			col=[]
  153. 			for j in range(config.WIDTH):
  154. 				col.append(0)
  155. 			self.Map.append(col)
  156. 		self.startPoint=None
  157. 		self.endPoint=None
  158. 		self.search=None
  159. 		self.centerTimer=None
  160. 		self.yi=None
  161. 		self.special=None
  162. 		self.displayFlush=False
  163. 		super().__init__()
  164. 		print('初始化UI...')
  165. 		self.initUI()
  166. 	def initUI(self):
  167. 		#开始初始化UI部分
  168. 			#创建UI控件
  169. 		self.label_tips=QLabel("<p style='color:green'>使用说明：</p>右键单击格子选定起始点,左键格子选定格子为墙壁或删除墙壁。\n<p style='color:green'>颜色说明：</p>\n黄色代表起点，绿色代表终点，黑色代表墙壁，红色代表待搜索的open列表，灰色代表已搜索过的close列表，蓝色代表当前搜索到的路径",self)
  170. 		self.label_display=QLabel("",self)
  171. 		self.button_start=QPushButton("开始搜索",self)
  172. 		self.button_clearSE=QPushButton("重选起始点",self)
  173. 		self.button_clearWall=QPushButton("清空地图墙壁",self)
  174. 		self.button_saveMap=QPushButton("保存地图",self)
  175. 		self.button_loadMap=QPushButton("加载地图",self)
  176.  
  177.  
  178. 			#设置控件属性
  179. 		self.label_tips.setWordWrap(True)
  180. 		self.label_display.setWordWrap(True)
  181. 			#设置控件样式
  182. 		self.label_display.setStyleSheet("border:1px solid black")
  183. 		self.label_display.setAlignment(Qt.AlignLeft)
  184. 		self.label_display.setAlignment(Qt.AlignTop)
  185. 			#设置控件的尺寸和位置
  186. 		self.label_tips.resize(200,150)
  187. 		self.button_saveMap.resize(80,30)
  188. 		self.button_loadMap.resize(80,30)
  189. 		self.label_display.resize(200,300)
  190.  
  191. 		self.label_tips.move(100+(config.WIDTH-1)*config.blockLength,0)
  192. 		self.label_display.move(100+(config.WIDTH-1)*config.blockLength,400)
  193. 		self.button_start.move(100+(config.WIDTH-1)*config.blockLength,200)
  194. 		self.button_clearSE.move(100+(config.WIDTH-1)*config.blockLength,250)
  195. 		self.button_clearWall.move(100+(config.WIDTH-1)*config.blockLength,300)
  196. 		self.button_saveMap.move(100+(config.WIDTH-1)*config.blockLength,350)
  197. 		self.button_loadMap.move(200+(config.WIDTH-1)*config.blockLength,350)
  198. 			#给控件绑定事件
  199. 		self.button_start.clicked.connect(self.button_StartEvent)
  200. 		self.button_clearSE.clicked.connect(self.button_Clear)
  201. 		self.button_clearWall.clicked.connect(self.button_Clear)
  202. 		self.button_saveMap.clicked.connect(self.button_SaveMap)
  203. 		self.button_loadMap.clicked.connect(self.button_LoadMap)
  204. 		#UI初始化完成
  205. 		self.setGeometry(0, 0, 150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
  206. 		self.setMinimumSize(150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
  207. 		self.setMaximumSize(150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
  208. 		self.setWindowTitle('A*搜索')
  209. 		self.show()
  210. 	def addDisplayText(self,text):
  211. 		if self.displayFlush:
  212. 			self.label_display.setText(text+'\n')
  213. 			self.displayFlush=False
  214. 		else:
  215. 			self.label_display.setText(self.label_display.text()+text+'\n')
  216. 	def mousePressEvent(self,event):
  217. 		x,y=event.x()-50,event.y()-50
  218. 		x=x//config.blockLength
  219. 		y=y//config.blockLength
  220. 		if x>=0 and x<config.WIDTH and y>=0 and y<config.HEIGHT:
  221. 			if event.button()==Qt.LeftButton:
  222. 				if (x,y)!=self.startPoint and (x,y)!=self.endPoint:
  223. 					self.Map[y][x]=(1 if self.Map[y][x]==0 else 0)
  224. 			if event.button()==Qt.RightButton:
  225. 				if self.Map[y][x]==0:
  226. 					if self.startPoint==None:
  227. 						self.startPoint=(x,y)
  228. 						self.addDisplayText('添加了一个起点:(%d,%d)'%(x,y))
  229. 					elif self.endPoint==None and self.startPoint!=(x,y):
  230. 						self.endPoint=(x,y)
  231. 						self.addDisplayText('添加了一个终点:(%d,%d)'%(x,y))
  232. 			self.repaint()
  233. 	def button_StartEvent(self):
  234. 		sender=self.sender()
  235. 		print(sender)
  236. 		if self.startPoint!=None and self.endPoint!=None:
  237. 			if self.centerTimer==None:
  238. 				self.centerTimer=QBasicTimer()
  239. 			self.button_start.setEnabled(False)
  240. 			self.button_clearSE.setEnabled(False)
  241. 			self.button_clearWall.setEnabled(False)
  242. 			self.centerTimer.start(200,self)
  243. 			self.search=A_Search(point(self.startPoint[1],self.startPoint[0]),point(self.endPoint[1],self.endPoint[0]),self.Map)
  244. 			self.yi=self.search.process()
  245. 			self.addDisplayText('开始进行搜索')
  246. 	def button_SaveMap(self):
  247. 		with open('map.txt','w') as f:
  248. 			f.write(json.dumps(self.Map))
  249. 			self.addDisplayText('地图保存成功-->map.txt')
  250. 		# else:
  251. 			# self.addDisplayText('地图保存失败')
  252. 	def button_LoadMap(self):
  253. 		try:
  254. 			with open('map.txt','r') as f:
  255. 				self.Map=json.loads(f.read())
  256. 				config.HEIGHT=len(self.Map)
  257. 				config.WIDTH=len(self.Map[0])
  258. 				self.addDisplayText('地图加载成功')
  259. 				self.repaint()
  260. 		except Exception as e:
  261. 			print('失败',e,type(e))
  262. 			if type(e)==FileNotFoundError:
  263. 				self.addDisplayText('地图加载失败:地图文件不存在')
  264. 			elif type(e)==json.decoder.JSONDecodeError:
  265. 				self.addDisplayText('地图加载失败:错误的地图文件')
  266. 	def button_Clear(self):
  267. 		sender=self.sender()
  268. 		print(self.button_clearSE,type(self.button_clearSE))
  269. 		if sender==self.button_clearSE:
  270. 			self.startPoint=None
  271. 			self.endPoint=None
  272. 			self.repaint()
  273. 			self.addDisplayText('清空起始点')
  274. 		elif sender==self.button_clearWall:
  275. 			for i in range(len(self.Map)):
  276. 				for j in range(len(self.Map[i])):
  277. 					self.Map[i][j]=0
  278. 			self.repaint()
  279. 			self.addDisplayText('清空所有墙壁')
  280. 	def paintEvent(self, event):
  281. 		qp = QPainter()
  282. 		qp.begin(self)
  283. 		self.drawBoard(event,qp)
  284. 		qp.end()
  285. 	def drawBoard(self, event, qp):
  286. 	    self.drawMap(qp)
  287. 	def drawMap(self,qp):#画面绘制方法，每次地图有所改动都将重绘
  288. 		time1=time.time()
  289. 		if self.search!=None:
  290. 			if self.special!=None:
  291. 				e=self.special[0]
  292. 				path=[e]
  293. 				while True:
  294. 					e=e.father
  295. 					if e!=None:
  296. 						path.append(e)
  297. 					else:
  298. 						break
  299. 			else:
  300. 				path=None
  301. 			pen=QPen(QColor(0,0,0),1,Qt.SolidLine)
  302. 			qp.setPen(pen)
  303. 			for i in range(len(self.Map)):
  304. 				for j in range(len(self.Map[i])):
  305. 					wordTag=False
  306. 					if i==self.search.start.x and j==self.search.start.y:
  307. 						qp.setBrush(QColor(255,255,0))
  308. 					elif i==self.search.end.x and j==self.search.end.y:
  309. 						qp.setBrush(QColor(100,200,50))
  310. 					else:
  311. 						if self.Map[i][j]==0:
  312. 							tagx=True
  313. 							if path:
  314. 								for k in path:
  315. 									if k.x==i and k.y==j:
  316. 										tagx=False
  317. 										qp.setBrush(QColor(0,100,255))
  318. 							if tagx:
  319. 								if self.special!=None:
  320. 									if i==self.special[0].x and j==self.special[0].y:
  321. 										qp.setBrush(QColor(0,255,0))
  322. 									else:
  323. 										tag=True
  324. 										for k in self.special[1]:
  325. 											if k.x==i and k.y==j:
  326. 												tag=False
  327. 												wordTag=True
  328. 												word=str(k.F)
  329.  
  330. 												qp.setBrush(QColor(150,0,0))
  331. 												break
  332. 											else:
  333. 												qp.setBrush(QColor(220,220,220))
  334. 										if tag:
  335. 											for k in self.special[2]:
  336. 												if k.x==i and k.y==j:
  337. 													qp.setBrush(QColor(150,150,150))
  338. 													break
  339. 												else:
  340. 													qp.setBrush(QColor(220,220,220))
  341. 								else:
  342. 									qp.setBrush(QColor(220,220,220))
  343. 						elif self.Map[i][j]==1:
  344. 							qp.setBrush(QColor(0,0,0))
  345. 						else:
  346. 							qp.setBrush(QColor(255,0,0))
  347. 					qp.drawRect(50+j*config.blockLength,50+i*config.blockLength,config.blockLength,config.blockLength)
  348. 					if wordTag:
  349. 						qp.setFont(QFont('楷体',5,QFont.Light))
  350. 						qp.drawText(50+10+j*config.blockLength,50+10+i*config.blockLength,word)
  351. 						wordTag=False
  352. 		#time.sleep(20)
  353. 		else:
  354. 			for i in range(len(self.Map)):
  355. 				for j in range(len(self.Map[i])):
  356. 					if (j,i)==self.startPoint:
  357. 						qp.setBrush(QColor(255,255,0))
  358. 					elif (j,i)==self.endPoint:
  359. 						qp.setBrush(QColor(100,200,50))
  360. 					else:
  361. 						if self.Map[i][j]==0:
  362. 							qp.setBrush(QColor(220,220,220))
  363. 						elif self.Map[i][j]==1:
  364. 							qp.setBrush(QColor(0,0,0))
  365. 						else:
  366. 							qp.setBrush(QColor(255,0,0))
  367.  
  368. 					qp.drawRect(50+j*config.blockLength,50+i*config.blockLength,config.blockLength,config.blockLength)
  369. 		time2=time.time()
  370. 	#time.sleep(20)
  371. 		# print('绘制时间：',time2-time1)
  372. 	def timerEvent(self,e):
  373. 		try:
  374. 			data=next(self.yi)
  375. 		except Exception as e:
  376. 			self.addDisplayText('搜索结束:')
  377. 			print('搜索结束！')
  378. 			if self.search.result==None:
  379. 				self.addDisplayText('未找到可行路径')
  380. 				print('搜索结束！')
  381. 			else:
  382. 				self.addDisplayText('总计搜索节点数：%d'%self.search.count)
  383. 				self.addDisplayText('最终路径长度：%d'%len(self.search.result))
  384. 			self.centerTimer.stop()
  385. 			self.search=None
  386. 			self.yi=None
  387. 			self.special=None
  388. 			point.clear()
  389. 			self.button_start.setEnabled(True)
  390. 			self.button_clearSE.setEnabled(True)
  391. 			self.button_clearWall.setEnabled(True)
  392. 			self.displayFlush=True
  393. 		else:
  394. 			self.special=data
  395. 			self.repaint()
  396. if __name__ == '__main__':
  397. 	app = QApplication(sys.argv)
  398. 	ex = GameBoard()
  399. 	sys.exit(app.exec_())

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

运行结果 

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

 

 详细列表

  1. 初始化地图...
  2. 初始化UI...
  3. <PyQt5.QtWidgets.QPushButton object at 0x0000017CC699AC18>
  4. 计算值： (2,3)[F=0,G=0,cost=10][father:((2, 2))]
  5. F=40 G=10 H=30
  6. 计算值： (3,3)[F=0,G=0,cost=14][father:((2, 2))]
  7. F=54 G=14 H=40
  8. 计算值： (3,2)[F=0,G=0,cost=10][father:((2, 2))]
  9. F=60 G=10 H=50
  10. 计算值： (3,1)[F=0,G=0,cost=14][father:((2, 2))]
  11. F=74 G=14 H=60
  12. 计算值： (2,1)[F=0,G=0,cost=10][father:((2, 2))]
  13. F=60 G=10 H=50
  14. 计算值： (1,1)[F=0,G=0,cost=14][father:((2, 2))]
  15. F=74 G=14 H=60
  16. 计算值： (1,2)[F=0,G=0,cost=10][father:((2, 2))]
  17. F=60 G=10 H=50
  18. 计算值： (1,3)[F=0,G=0,cost=14][father:((2, 2))]
  19. F=54 G=14 H=40
  20. 计算值： (3,3)[F=54,G=14,cost=10][father:((2, 3))]
  21. F=60 G=20 H=40
  22. 计算值： (3,2)[F=60,G=10,cost=14][father:((2, 3))]
  23. F=74 G=24 H=50
  24. 计算值： (1,2)[F=60,G=10,cost=14][father:((2, 3))]
  25. F=74 G=24 H=50
  26. 计算值： (1,3)[F=54,G=14,cost=10][father:((2, 3))]
  27. F=60 G=20 H=40
  28. 计算值： (4,4)[F=0,G=0,cost=14][father:((3, 3))]
  29. F=68 G=28 H=40
  30. 计算值： (4,3)[F=0,G=0,cost=10][father:((3, 3))]
  31. F=74 G=24 H=50
  32. 计算值： (4,2)[F=0,G=0,cost=14][father:((3, 3))]
  33. F=88 G=28 H=60
  34. 计算值： (3,2)[F=60,G=10,cost=10][father:((3, 3))]
  35. F=74 G=24 H=50
  36. 计算值： (1,2)[F=60,G=10,cost=10][father:((1, 3))]
  37. F=74 G=24 H=50
  38. 计算值： (0,2)[F=0,G=0,cost=14][father:((1, 3))]
  39. F=88 G=28 H=60
  40. 计算值： (0,3)[F=0,G=0,cost=10][father:((1, 3))]
  41. F=74 G=24 H=50
  42. 计算值： (0,4)[F=0,G=0,cost=14][father:((1, 3))]
  43. F=68 G=28 H=40
  44. 计算值： (4,3)[F=74,G=24,cost=14][father:((3, 2))]
  45. F=74 G=24 H=50
  46. 计算值： (4,2)[F=88,G=28,cost=10][father:((3, 2))]
  47. F=80 G=20 H=60
  48. 计算值： (4,1)[F=0,G=0,cost=14][father:((3, 2))]
  49. F=94 G=24 H=70
  50. 计算值： (3,1)[F=74,G=14,cost=10][father:((3, 2))]
  51. F=80 G=20 H=60
  52. 计算值： (2,1)[F=60,G=10,cost=14][father:((3, 2))]
  53. F=74 G=24 H=50
  54. 计算值： (3,1)[F=74,G=14,cost=10][father:((2, 1))]
  55. F=80 G=20 H=60
  56. 计算值： (3,0)[F=0,G=0,cost=14][father:((2, 1))]
  57. F=94 G=24 H=70
  58. 计算值： (2,0)[F=0,G=0,cost=10][father:((2, 1))]
  59. F=80 G=20 H=60
  60. 计算值： (1,0)[F=0,G=0,cost=14][father:((2, 1))]
  61. F=94 G=24 H=70
  62. 计算值： (1,1)[F=74,G=14,cost=10][father:((2, 1))]
  63. F=80 G=20 H=60
  64. 计算值： (1,2)[F=60,G=10,cost=14][father:((2, 1))]
  65. F=74 G=24 H=50
  66. 计算值： (1,1)[F=74,G=14,cost=10][father:((1, 2))]
  67. F=80 G=20 H=60
  68. 计算值： (0,1)[F=0,G=0,cost=14][father:((1, 2))]
  69. F=94 G=24 H=70
  70. 计算值： (0,2)[F=88,G=28,cost=10][father:((1, 2))]
  71. F=80 G=20 H=60
  72. 计算值： (0,3)[F=74,G=24,cost=14][father:((1, 2))]
  73. F=74 G=24 H=50
  74. 计算值： (4,5)[F=0,G=0,cost=10][father:((4, 4))]
  75. F=68 G=38 H=30
  76. 计算值： (5,5)[F=0,G=0,cost=14][father:((4, 4))]
  77. F=82 G=42 H=40
  78. 计算值： (5,4)[F=0,G=0,cost=10][father:((4, 4))]
  79. F=88 G=38 H=50
  80. 计算值： (5,3)[F=0,G=0,cost=14][father:((4, 4))]
  81. F=102 G=42 H=60
  82. 计算值： (4,3)[F=74,G=24,cost=10][father:((4, 4))]
  83. F=88 G=38 H=50
  84. 计算值： (3,5)[F=0,G=0,cost=14][father:((4, 4))]
  85. F=62 G=42 H=20
  86. 计算值： (3,6)[F=0,G=0,cost=10][father:((3, 5))]
  87. F=62 G=52 H=10
  88. 计算值： (4,6)[F=0,G=0,cost=14][father:((3, 5))]
  89. F=76 G=56 H=20
  90. 计算值： (4,5)[F=68,G=38,cost=10][father:((3, 5))]
  91. F=82 G=52 H=30
  92. 计算值： (2,5)[F=0,G=0,cost=10][father:((3, 5))]
  93. F=62 G=52 H=10
  94. 计算值： (2,6)[F=0,G=0,cost=14][father:((3, 5))]
  95. F=56 G=56 H=0
  96. 搜索结束！

可执行文件

已经将程序打包成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

————————————————
版权声明：本文为CSDN博主「Clark-dj」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/dujuancao11/article/details/109749219

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/218677
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号