学习笔记.

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()