当前位置: 代码迷 >> 综合 >> 03-0002 Python实现A*算法
  详细解决方案

03-0002 Python实现A*算法

热度:10   发布时间:2023-11-24 02:01:09.0

Python实现A*算法

  • 1.算法描述
  • 2.问题描述
  • 3.算法原理
  • 4.算法源码
  • 5.算法输出
  • 6.总结

1.算法描述

A*搜寻算法俗称A星算法,是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度。

A*改变它自己行为的能力基于启发式代价函数,启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中,你并不真正需要得到最好的路径,仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么,或者运行游戏的机器有多快。

在本实验中,为了解决罗马尼亚度假问题而引入的A算法,目的是为了寻找一个城市到另一个城市的最短路径,A算法

扩展:本来想些启发式算法的,但是突然迷茫了一下,可以以后再写,好好的学一学。当我写这些东西的时候,我发现,自己还不是很懂。
以上多数文字直接来源于度娘百科,没有过多的修改。我对于A*算法的描述,着实少之又少,感觉自己又回到了最初的懵懂状态。
我需要一个比较好的数据集来解释自己想要时候的,直接用数据来描述自己想要表达的。

2.问题描述

旅行商问题:
In the following map with 20 cities, please find a route from Zerind to Bucharest using A search.*
[在一个拥有20个城市的图中,使用A星算法,找到一条最优路径从塞尔维亚到罗马尼亚]
在这里插入图片描述
解释:

上述图中,线上的数字表示两个城市的实际距离。
右侧的数字表示到Bucharest[终点]的估计距离。
每个城市的首字母都不一样,可以数字化。

3.算法原理

A*算法是一种搜索算法,在算法过程中引入了F,G,H三个量。
F=G+HF=G+HF=G+H

F:用作判断条件的量。在算法使用的数据结构[优先级队列]中,F小的将会先弹出。F:用作判断条件的量。在算法使用的数据结构[优先级队列]中,F小的将会先弹出。F使[]F
G:从出发点到当前节点的实际距离。G:从出发点到当前节点的实际距离。G
H:从当前节点到目标节点的估计距离。H:从当前节点到目标节点的估计距离。H

下面引入具体数据,来演示A*算法:
.在这里插入图片描述
说明:

pS12:P节点的F值是12,父节点是Sp_{S}^{12}:P节点的F值是12,父节点是SpS12?PF12S
PQ:优先级队列PQ:优先级队列PQ
SK:栈SK:栈SK

注意事项:

1.每次进入PQ的结点是上一次从PQ弹出结点的临近结点。1.每次进入PQ的结点是上一次从PQ弹出结点的临近结点。1.PQPQ
2.从PQ中弹出的结点放入SK中2.从PQ中弹出的结点放入SK中2.PQSK
3.进入PQ的结点若已经存在,比较F值,小的留下3.进入PQ的结点若已经存在,比较F值,小的留下3.PQF
4.已经存在于SK中的结点不进入PQ中4.已经存在于SK中的结点不进入PQ中4.SKPQ
5.到达目标结点就终止运算5.到达目标结点就终止运算5.

过程:

PQ:Snone12PQ:S_{none}^{12}PQSnone12?
SK:noneSK:noneSKnone
.
PQ:Snone12,ds12,es13,ps12PQ:\bcancel{S_{none}^{12}},d_{s}^{12},e_{s}^{13},p_{s}^{12}PQSnone12? ?ds12?es13?ps12?
SK:SSK:SSKS
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,ps12,bd15,cd16,ed9\xcancel{e_{s}^{13}},p_{s}^{12},b_{d}^{15},c_{d}^{16},e_{d}^{9}es13? ?ps12?bd15?cd16?ed9? [这里需要替换e结点][这里需要替换e结点][e]
SK:S,dSK:S,dSKSd
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,ps12,bd15,cd16,\xcancel{e_{s}^{13}},p_{s}^{12},b_{d}^{15},c_{d}^{16},es13? ?ps12?bd15?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,h_{e}^{12},he12? re20r_{e}^{20}re20? [此时弹出p,h皆可][此时弹出p,h皆可][ph]
SK:S,d,eSK:S,d,eSKSde
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,b_{d}^{15},c_{d}^{16},bd15?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,h_{e}^{12},he12? re20r_{e}^{20}re20?qp25q_{p}^{25}qp25?
SK:S,d,e,pSK:S,d,e,pSKSdep
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,b_{d}^{15},c_{d}^{16},bd15?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,\bcancel{h_{e}^{12}},he12? ? re20r_{e}^{20}re20?qp25\xcancel{q_{p}^{25}}qp25? ?qh19q_{h}^{19}qh19? [此时p在SK,q在PQ,p不进,q换掉][此时p在SK,q在PQ,p不进,q换掉][pSKqPQpq]
SK:S,d,e,p,hSK:S,d,e,p,hSKSdeph
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,\bcancel{b_{d}^{15}},c_{d}^{16},bd15? ?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,\bcancel{h_{e}^{12}},he12? ? re20r_{e}^{20}re20?qp25\xcancel{q_{p}^{25}}qp25? ?qh19q_{h}^{19}qh19?ab14a_{b}^{14}ab14?
SK:S,d,e,p,h,bSK:S,d,e,p,h,bSKSdephb
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,\bcancel{b_{d}^{15}},c_{d}^{16},bd15? ?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,\bcancel{h_{e}^{12}},he12? ? re20r_{e}^{20}re20?qp25\xcancel{q_{p}^{25}}qp25? ?qh19q_{h}^{19}qh19?ab14\bcancel{a_{b}^{14}}ab14? ? [a没有临近结点,弹出下一个][a没有临近结点,弹出下一个][a]
SK:S,d,e,p,h,b,aSK:S,d,e,p,h,b,aSKSdephba
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,\bcancel{b_{d}^{15}},c_{d}^{16},bd15? ?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,\bcancel{h_{e}^{12}},he12? ? re20\xcancel{r_{e}^{20}}re20? ?qp25\xcancel{q_{p}^{25}}qp25? ?qh19\bcancel{q_{h}^{19}}qh19? ?ab14\bcancel{a_{b}^{14}}ab14? ?rq19r_{q}^{19}rq19?
SK:S,d,e,p,h,b,a,qSK:S,d,e,p,h,b,a,qSKSdephbaq
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,\bcancel{b_{d}^{15}},c_{d}^{16},bd15? ?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,\bcancel{h_{e}^{12}},he12? ? re20\xcancel{r_{e}^{20}}re20? ?qp25\xcancel{q_{p}^{25}}qp25? ?qh19\bcancel{q_{h}^{19}}qh19? ?ab14\bcancel{a_{b}^{14}}ab14? ?rq19\bcancel{r_{q}^{19}}rq19? ?fr18f_{r}^{18}fr18?
SK:S,d,e,p,h,b,a,q,rSK:S,d,e,p,h,b,a,q,rSKSdephbaqr
.
PQ:Snone12,PQ:\bcancel{S_{none}^{12}},PQSnone12? ? ds11,\bcancel{d_{s}^{11}},ds11? ? es13,\xcancel{e_{s}^{13}},es13? ? ps12\bcancel{p_{s}^{12}}ps12? ?bd15,cd16,\bcancel{b_{d}^{15}},c_{d}^{16},bd15? ?cd16?ed9,\bcancel{e_{d}^{9}},ed9? ? he12,\bcancel{h_{e}^{12}},he12? ? re20\xcancel{r_{e}^{20}}re20? ?qp25\xcancel{q_{p}^{25}}qp25? ?qh19\bcancel{q_{h}^{19}}qh19? ?ab14\bcancel{a_{b}^{14}}ab14? ?rq19\bcancel{r_{q}^{19}}rq19? ?fr24\bcancel{f_{r}^{24}}fr24? ?cf25c_{f}^{25}cf25?Gf23G_{f}^{23}Gf23? [得到了G进行终止][得到了G进行终止][G]
SK:S,d,e,p,h,b,a,q,r,fSK:S,d,e,p,h,b,a,q,r,fSKSdephbaqrf
.

回溯:Gf23G_{f}^{23}Gf23?fr24\bcancel{f_{r}^{24}}fr24? ?rq19\bcancel{r_{q}^{19}}rq19? ?qh19\bcancel{q_{h}^{19}}qh19? ?he12\bcancel{h_{e}^{12}}he12? ?ed9\bcancel{e_{d}^{9}}ed9? ?ds11\bcancel{d_{s}^{11}}ds11? ?Snone12\bcancel{S_{none}^{12}}Snone12? ?
最终结果:S→d→e→h→q→r→f→GS\rightarrow d\rightarrow e\rightarrow h\rightarrow q\rightarrow r\rightarrow f\rightarrow GSdehqrfG

具体的实验过程中需要用某种数据结构来保存父节点,以便回溯,而且最终G结点的F值,就是实际路程。自我感觉良好,上面的那一段我输入了好长时间。不知道是什么原因,过程特别的卡顿,我猜是因为要解析好多的符号,可能需要消耗时间,比较少的时候还好,很多的话,就不如插入一张图片。这也是浏览器加载的时候需要注意的,加载一张图远比加载好多图来得快,所以会将好多图标都绘制在一张图上,在网页中只显示图片中的某一部分,这样一来,打开这样的网页,图片就只加载了一次。

流程图如下:
在这里插入图片描述

这是很久以前绘制的流程图,可能不是很准确但是是根据伪代码画出来的,应该不会有错。

伪代码:
在这里插入图片描述

4.算法源码

#!/usr/bin/python
# -*- coding: UTF-8 -*-# redefine place
A = 0  # Arad
B = 1  # Bucharest
C = 2  # Craiova
D = 3  # Dobreta
E = 4  # Eforie
F = 5  # Fagaras
G = 6  # Giurgiu
H = 7  # Hirsova
I = 8  # Iasi
L = 9  # Lugoj
M = 10  # Mehadia
N = 11  # Neamt
O = 12  # Oradea
P = 13  # Pitesti
R = 14  # Rimnicu Vilcea
S = 15  # Sibiu
T = 16  # Timisoara
U = 17  # Urziceni
V = 18  # Vaslui
Z = 19  # Zerind# 构建一个20*20的矩阵PLACES_NUM = 20# 地图
class Graph:def __init__(self):self.romania_graph = [[0] * PLACES_NUM for i in range(PLACES_NUM)]def add_edge(self, _from, _to, _value):if _from < PLACES_NUM:if _to < PLACES_NUM:self.romania_graph[_from][_to] = _valueself.romania_graph[_to][_from] = _valuedef get_edge(self, _from, _to):return self.romania_graph[_from][_to]#问题的最终解
class Stack:def __init__(self):self.stack = []def push(self, value):self.stack.append(value)returndef pop(self):return self.stack.pop()def is_empty(self):if self.stack:return Falsereturn True# CLOSED表
class Queue:def __init__(self):self.queue = []def put(self, value):self.queue.append(value)returndef get(self):return self.queue.pop(0)def contain(self, value):return value in self.queuedef is_empty(self):if self.queue:return Falsereturn True# OPEN表
class PriorityQueue:def __init__(self):self.queue = []def put(self, node_cost):""":param node_cost: [value,cost]"""self.queue.append(node_cost)def get(self):if self.queue:min_i = 0min_cost = self.queue[min_i][1]for i in range(len(self.queue)):if self.queue[i][1] < min_cost:min_i = imin_cost = self.queue[i][1]return self.queue.pop(min_i)def contain(self,value):for i in range(len(self.queue)):if self.queue[i][0]==value:return self.queue[i],Truereturn None,Falsedef is_empty(self):if self.queue:return Falsereturn True# initialize undirected graph
# 初始化无向图
def init_graph():graph = Graph()graph.add_edge(O, Z, 71)graph.add_edge(O, S, 151)graph.add_edge(A, Z, 75)graph.add_edge(A, S, 140)graph.add_edge(A, T, 118)graph.add_edge(T, L, 111)graph.add_edge(L, M, 70)graph.add_edge(M, D, 75)graph.add_edge(D, C, 120)graph.add_edge(S, R, 80)graph.add_edge(S, F, 99)graph.add_edge(R, C, 146)graph.add_edge(F, B, 211)graph.add_edge(R, P, 97)graph.add_edge(C, P, 138)graph.add_edge(P, B, 101)graph.add_edge(B, G, 90)graph.add_edge(B, U, 85)graph.add_edge(U, H, 98)graph.add_edge(U, V, 142)graph.add_edge(V, I, 92)graph.add_edge(I, N, 87)graph.add_edge(H, E, 86)return graphdef a_star(graph, h, _root, _goal):g = [0] * PLACES_NUM  # g(n) value 现阶段搜索过程中的每个结点的g(n)记录@parents = [0] * PLACES_NUM  # temporary parents 现阶段搜索过程中的每个节点的父结点记录@pq_open = PriorityQueue()  # open queue 初始化open表@q_close = Queue()  # closed queue 初始化closed表@s_path = Stack()  # solution nodes path s_path中作为走过路径记录@s_parent = Stack()  # solution nodes' parents path s_parent中作为open表每次pop的记录@pq_open.put([_root, 0])                                     #将初始结点存入OPEN表中@while pq_open.is_empty()==False:parrent_node=pq_open.get()if parrent_node[0]==_goal:breakq_close.put(parrent_node[0])for i in range(20):length=graph.get_edge(parrent_node[0],i)if length!=0:node,result=pq_open.contain(i)f=parrent_node[1]-h[parrent_node[0]]+length+h[i]if q_close.contain(i):continueelif result==True:if node[1]>f:node.pop()parents[i]=parrent_node[0]pq_open.put([i,f])else:parents[i]=parrent_node[0]pq_open.put([i,f])path=[]cost=0print("parents:",parents)p=_goalwhile p!=_root:cost+=graph.get_edge(p,parents[p])path.append(p);p=parents[p]length=len(path)-1print('path:',_root,end='')for i in range(length+1):print(" -->",path[length-i],end='')print()return costif __name__ == '__main__':graph = init_graph()# 怎么才能够获取到这个矩阵h = (366, 0, 160, 242, 161,178, 77, 151, 226, 244,241, 234, 380, 98, 193,253, 329, 80, 199, 374)# place_str = input()# places = place_str.split()# cost = a_star(graph, h, eval(places[0]), eval(places[1]))print("node","A"," B")cost = a_star(graph, h,eval('A'),eval('B'))print('cost:',cost)print()print("node","C"," B")cost = a_star(graph, h,eval('C'),eval('B'))print('cost:',cost)print()print("node","U"," B")cost = a_star(graph, h,eval('U'),eval('B'))print('cost:',cost)print()

备注:

  1. 保存好源码之后,自己多写几个print来看一看各个数据都是什么,避免超级低级的错误。
  2. 源码总注释比较少,为何?因为有了流程图,以及上面的展示,A*算法的思想还是很容易就可以理解的,而且算法部分的代码很容易就能够看懂。
  3. 话说我也不知道是为什么,我上传代码之后竟然没有高亮显示,感觉很奇怪,是不是我等级尚低,修为尚浅,还是因为之前的代码都是MATLAB代码。
  4. 代码最后的部分,注释掉的三行是用来控制台输入的,但是鉴于Sublime Text3中input()函数不好用,我直接弄成了固定的测试数据。
  5. 代码中最后的cost计算,可以直接从A*算法中得到,并不需要使用回溯的方法,所以我这里这样写,纯属画蛇添足,但是因为要输出路径,所以顺带算了一下

5.算法输出

在这里插入图片描述

6.总结

不难。但是却囿于有限的知识,而不能够将其进行扩展,A*算法是一种比较好的寻路算法,在游戏中会经常使用到,在Unity中有特定的寻路算法,也有一部分人是自己写的算法,自己写的话有什么好处呢?
倘若是自己写的寻路算法,在寻路的时候,可以给AI加上好多东西,这样可以让AI看上去不是那么傻?现在还是有一些疑惑的,寻路的时候是将地图当成了一个类似于坐标系一样的东西,中间遇到障碍物就会换路,而且是找到一条路径之后,AI才会出发,也就是说AI提前就知道一条路径,o(  ̄︶ ̄ )o。
那么怎么把现在的这种数据跟游戏中寻路数据对应起来呢?好晕。找了一些个链接,有时间的时候可以看一看,或者就最近这一段时间看一看

链接如下:

  1. A星算法详解(个人认为最详细,最通俗易懂的一个版本)
  2. A* Pathfinding for Beginners(不用外网)
  3. 堪称最好最全的A*算法详解(译文)
  4. Amit’s A* Pages(不用外网)

应该尝试用各种编程语言写该算法,因为不能容忍自己的菜!!!