A* Search

其实就是带权的BFS，只是这里的权重不是朴素的距离相邻而是一种单独的标准即f = g + h

A* search算法和Dijkstra还有BFS的不同在于，后面两者都是可以计算单源多终点的算法，也就是说，当起点终点都是唯一时，这两种算法都有很多多余的计算量，而A*只是为了计算点对点耗费最少的路径（注意不是最短）而使用的算法，而Dijkstra本身是一种A*算法的特化，这里的一切还是基于上面的公式f = g + h，h为当前点到终点的估计耗费（通过函数算出），g为起点到当前点的耗费，而对于Dijkstra算法来说，h恒等于0，所以基本上A*算法的实现和Dijkstra非常类似

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
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

参考：

1. http://web.mit.edu/eranki/www/tutorials/search/
2. http://bit.ly/2zm7y9N（讲的详细且清楚，把BFS，Dijkstra，A*一步步由简单到复杂都覆盖了）
3. http://bit.ly/2AnaWPO（有完整的A* 算法实现的Python源代码）