A*算法
class Node: #定义Node结点类，城市抽象为结点
def __init__(self, name, parent, g, h, f): #初始化操作
self.name = name
self.parent = parent
self.g = g #到开始结点的距离
self.f = f #路径之和
class Graph: #定义一个Graph图类
def __init__(self, graph_dict=None): #初始化操作,graph_dict为字典
self.graph_dict = graph_dict or {}
def connect(self, A, B, distance): #输入A,B结点和之间的距离
self.graph_dict.setdefault(A, {})[B] = distance #将所有信息保存在字典中
def makegraph(self): #先创建图，然后添加距离
for a in list(self.graph_dict.keys()):
for (b, dist) in self.graph_dict[a].items():
self.graph_dict.setdefault(b, {})[a] = dist #改变字典的键值为dist，即距离
def getNode(self, city, heuristics, end): #得到代价最低的邻接城市
min = 999999 #初始化一个值
for (b,dist) in self.graph_dict[city].items():
if (dist+heuristics[b]) < min: #如果总代价小于min
min = dist+heuristics[b] #改变min的值
minnode = Node(city, b, dist, heuristics[b], dist+heuristics[b]) #得到代价最低的邻接城市，记录该节点的所有数据
return minnode #函数的返回值为代价最低的邻接城市
def A_Star(graph, heuristics, start, end): #定义A*算法
open_list = list() #创建空列表
path = list() #创建空列表
curr_node = graph.getNode(start,heuristics, end) #当前结点为总代价最小的邻接城市
open_list.append(curr_node) #在openlist中添加该结点
totalcost = 0 #初始化总代价为0
while(curr_node.name != end): #当总代价最小的邻接城市不是目的地的时候
totalcost += curr_node.g #总代价的值更新为当前总代价+当前结点到开始结点的距离
path.append(curr_node.name) #路径添加当前结点的名字即当前城市的名字
curr_node = graph.getNode(curr_node.parent,heuristics, end) #更新当前结点继续循环
if(curr_node.name == end): #如果当前结点为目的地结点
path.append(curr_node.name) #添加城市 结束循环
break
print("FINAL COST -> " + str(totalcost)) #打印总代价
return path #函数的返回值为路径
def main():
graph = Graph()
#将城市和真实距离构造为图
graph.connect('Arad', 'Zerind', 75)
graph.connect('Arad', 'Siblu', 140)
graph.connect('Arad', 'Timisoara', 118)
graph.connect('Zerind', 'Oradea', 71)
graph.connect('Oradea', 'Siblu', 151)
graph.connect('Siblu', 'Fugaras', 99)
graph.connect('Siblu', 'Rimnicu Vilcea', 80)
graph.connect('Rimnicu Vilcea', 'Pitesti', 97)
graph.connect('Timisoara', 'Lugoj', 111)
graph.connect('Lugoj','Mehadia', 70)
graph.connect('Mehadia', 'Dobreta',75)
graph.connect('Dobreta', 'Craiova', 120)
graph.connect('Craiova','Rimnicu Vilcea', 146)
graph.connect('Craiova','Pitesti', 138)
graph.connect('Fugaras', 'Bucharest', 211)
graph.connect('Pitesti', 'Bucharest', 101)
graph.connect('Giurgiu', 'Bucharest', 90)
graph.makegraph()
# 为每个结点添加到目的地Bucharest的启发式距离
heuristics = {}
heuristics['Arad'] = 366
heuristics['Bucharest'] = 0
heuristics['Craiova'] = 160
heuristics['Dobreta'] = 242
heuristics['Fugaras'] = 176
heuristics['Lugoj'] = 244
heuristics['Mehadia'] = 241
heuristics['Oradea'] = 380
heuristics['Pitesti'] = 10
heuristics['Rimnicu Vilcea'] = 193
heuristics['Siblu'] = 253
heuristics['Timisoara'] = 329
heuristics['Zerind'] = 374
heuristics['Giurgiu'] = 77
# 起点为Arad，目的地为Bucharest
path = A_Star(graph, heuristics, 'Arad', 'Bucharest')
print("PATH: " ,end = " ")
print(path)
# 运行程序
if __name__ == "__main__": main()
