博客

不同于Dijkstra算法只记录到起点的代价，

A*算法不但记录到起点的代价、还叠加到目标点的估计代价

，是一种

启发式算法

，也可以认为是一种

深度优先

的算法。

该算法的流程如下图所示（图片截自B站艾若机器人Joe的课程视频），图中的g代表当前点到起点的代价，h代表当前点到目标点的估计代价。

还是选择之前Dijkstra算法使用的那张图，利用A*算法寻找从节点1到节点5的最短路径，在之前图的基础上为每个节点增加到目标节点5的估计代价，如图中砖红色数字表示。

根据A*算法的思路，open list用于存放当前还没有找到最短路径的节点（从起点开始）、closed list用于存放已经找到最短路径的节点，具体的搜索过程如下表所示，表中的灰色表示从open list移动至closed list。

在之前Python代码的基础上略作修改，如下所示：

class Astar:
    def __init__(self, graph, start, goal):
        self.graph = graph      
        self.start = start      
        self.goal = goal        

        self.open_list = {}     
        self.closed_list = {}   

        self.open_list[start] = h[start] 

        self.parent = {start: None}     
        self.min_dis = None            

    def shortest_path(self):

        while True:
            if self.open_list is None:
                print('搜索失败， 结束！')
                break
            distance, min_node = min(zip(self.open_list.values(), self.open_list.keys()))      
            self.open_list.pop(min_node)                                                       
            
            print('open list:{}'.format(self.open_list))          

            self.closed_list[min_node] = distance                  
            print('closed list:{}'.format(self.closed_list))
            print('min node:{}'.format(min_node))
            print('--------------------------------------------------------------------------')
            if min_node == self.goal:                              
                self.min_dis = distance
                shortest_path = [self.goal]                        
                father_node = self.parent[self.goal]
                while father_node != self.start:
                    shortest_path.append(father_node)
                    father_node = self.parent[father_node]
                shortest_path.append(self.start)
                print(shortest_path[::-1])                        
                print('最短路径的长度为：{}'.format(self.min_dis))
                print('找到最短路径， 结束！')
                return shortest_path[::-1], self.min_dis			

            for node in self.graph[min_node].keys():             
                if node not in self.closed_list.keys():  
                    if node in self.open_list.keys():             
                        if self.graph[min_node][node] + distance + h[node] - h[min_node] < self.open_list[node]:
                            self.open_list[node] = distance + self.graph[min_node][node] + h[node] - h[min_node]    
                            self.parent[node] = min_node         
                    else:                                          
                        self.open_list[node] = distance + self.graph[min_node][node] + h[node] - h[min_node]            
                        self.parent[node] = min_node             


if __name__ == '__main__':
    g = {'1': {'2': 2, '4': 1},
         '2': {'4': 3, '5': 11},
         '3': {'1': 4, '6': 5},
         '4': {'3': 2, '6': 8, '7': 4},
         '5': {'7': 6},
         '7': {'6': 1},
         '6': {'6': 0}
         }
    h = {'1':3,'2':3,'3':20,'4':15,'5':0,'6':10,'7':20}
    start = '1'
    goal = '5'
    astar = Astar(g, start, goal)
    astar.shortest_path()

代码的执行结果如下所示，与之前给出的搜索结果一致。可以看出，

相比于Dijkstra算法，A*算法能够更快地找到最短路径

。

需要注意的是，

如果h的取值不合理，有可能选择的路径不是最优的

。