Maison > développement back-end > Tutoriel Python > Découvrez les étapes détaillées pour implémenter l'algorithme A* en Python

Découvrez les étapes détaillées pour implémenter l'algorithme A* en Python

PHPz
Libérer: 2024-01-23 22:51:05
avant
780 Les gens l'ont consulté

以此加权图为例,用Python实现A*算法。加权图中的节点用粉红色圆圈表示,并且给出了沿节点的路径的权重。节点上方的数字代表节点的启发式值。

Découvrez les étapes détaillées pour implémenter lalgorithme A* en Python

首先为算法创建类。一个用于存储与起始节点的距离,另一个用于存储父节点。并将它们初始化为0,以及起始节点。

def aStarAlgo(start_node,stop_node):
open_set=set(start_node)
closed_set=set()
g={}
parents={}
g[start_node]=0
parents[start_node]=start_node
Copier après la connexion

找到具有最低f(n)值的相邻节点,针对到达目标节点的条件进行编码。如果不是这种情况,则将当前节点放入打开列表中,并设置其父节点。

While len(open_set)>0:
n=None
for v in open_set:
if n==None or g[v]+heuristic(v)<g[n]+heuristic(n):
n=v
if n==stop_node or Graph_nodes[n]==None:
pass
else:
for(m,weight)in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m]=n
g[m]=g[n]+weight
Copier après la connexion

如果相邻的g值低于当前节点并且在封闭列表中,则将其替换为这个新节点作为父节点。

else:
if g[m]>g[n]+weight:
g[m]=g[n]+weight
parents[m]=n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
Copier après la connexion

如果当前g低于前一个g,并且其相邻在open list中,则将其替换为较低的g值,并将相邻的parent更改为当前节点。

如果不在两个列表中,则将其添加到打开列表并设置其g值。

if n==None:
print(&#x27;Path does not exist!&#x27;)
return None
if n==stop_node:
path=[]
while parents[n]!=n:
path.append(n)
n=parents[n]
path.append(start_node)
path.reverse()
print(&#x27;Path found:{}&#x27;.format(path))
return path
open_set.remove(n)
closed_set.add(n)
print(&#x27;Path does not exist!&#x27;)
return None
Copier après la connexion

现在,定义一个函数来返回相邻节点及其距离。

def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
Copier après la connexion

此外,创建一个函数来检查启发式值。

def heuristic(n):
H_dist={
&#x27;A&#x27;:11,
&#x27;B&#x27;:6,
&#x27;C&#x27;:99,
&#x27;D&#x27;:1,
&#x27;E&#x27;:7,
&#x27;G&#x27;:0,
}
return H_dist[n]
Copier après la connexion

描述一下图表并调用A*函数。

Graph_nodes={
&#x27;A&#x27;:[(&#x27;B&#x27;,2),(&#x27;E&#x27;,3)],
&#x27;B&#x27;:[(&#x27;C&#x27;,1),(&#x27;G&#x27;,9)],
&#x27;C&#x27;:Node,
&#x27;E&#x27;:[(&#x27;D&#x27;,6)],
&#x27;D&#x27;:[(&#x27;G&#x27;,1)],
}
aStarAlgo(&#x27;A&#x27;,&#x27;G&#x27;)
Copier après la connexion

算法遍历图,找到代价最小的路径。

这是通过E => D => G。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal