A*算法（A star算法）

A算法(念作A star算法)是一种路径规划中常用的算法。如果你知道Dijkstra算法，那么恭喜你，A*算法是Dijkstra算法的延申版，区别仅仅在于把priority从离起点的距离 f(n) 再加上了一个heuristic函数 h(n)。通常h(n)可以取到达目的地的欧氏距离。 Red Blob提供的伪代码如下:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

A*算法通过h(n)提升了对最短路径的搜索效率： ## Reference

• [1] A star algorithm - Red Blob
• [2] Dijkstra算法