学习Python中A*算法实现的详细步骤
以此加权图为例，用Python实现A*算法。加权图中的节点用粉红色圆圈表示，并且给出了沿节点的路径的权重。节点上方的数字代表节点的启发式值。
首先为算法创建类。一个用于存储与起始节点的距离，另一个用于存储父节点。并将它们初始化为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登录后复制
While len(open_set)>0:
n=None
for v in open_set:
if n==None or g[v]+heuristic(v) 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)登录后复制 如果不在两个列表中，则将其添加到打开列表并设置其g值。 if n==None:
print('Path does not exist!')
return None
if 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 path
open_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]登录后复制 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*算法实现的详细步骤的详细内容，更多请关注每日运维网(www.mryunwei.com)其它相关文章！
