学习Python中A*算法实现的详细步骤

百变鹏仔 1天前 #Python

文章标签算法

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

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

def aStarAlgo(start_node,stop_node):open_set=set(start_node)closed_set=set()g={}parents={}g[start_node]=0parents[start_node]=start_node

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

立即学习“Python免费学习笔记（深入）”；

While len(open_set)&gt;0:n=Nonefor v in open_set:if n==None or g[v]+heuristic(v)<g n="v" if or graph_nodes pass else: for get_neighbors m not in open_set and closed_set: open_set.add parents g><p>如果相邻的g值低于当前节点并且在封闭列表中，则将其替换为这个新节点作为父节点。</p><pre class="brush:php;toolbar:false;">else:if g[m]&gt;g[n]+weight:g[m]=g[n]+weightparents[m]=nif m in closed_set:closed_set.remove(m)open_set.add(m)

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

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

if n==None:print('Path does not exist!')return Noneif n==stop_node:path=[]while parents[n]!=n:path.append(n)n=parents[n]path.append(start_node)path.reverse()print('Path found:{}'.format(path))return pathopen_set.remove(n)closed_set.add(n)print('Path does not exist!')return None

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

def get_neighbors(v):if v in Graph_nodes:return Graph_nodes[v]else:return None

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

def heuristic(n):H_dist={'A':11,'B':6,'C':99,'D':1,'E':7,'G':0,}return H_dist[n]

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

Graph_nodes={'A':[('B',2),('E',3)],'B':[('C',1),('G',9)],'C':Node,'E':[('D',6)],'D':[('G',1)],}aStarAlgo('A','G')

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

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

文章推荐

学习Python中A*算法实现的详细步骤

Python日志基础 - 简易指南

如何在Python中创建静态类数据和静态类方法？

使用Python获取字符串列表中数字的总和

如何使用TensorFlow Serving在Python中部署模型？

Python程序：删除数组/列表中的所有元素的出现次数