路径规划之A*算法

我们来认真复盘一下Astar算法
Astar = 迪佳斯特拉 + BFS
迪佳斯特拉算法：如果每一步的权重均设置为1，那么我们的算法就是一圈一圈的往外走，广度优先。因为它只考虑眼前和过去，怎么能走的最短。
而bfs最佳优先搜索算法属于贪婪算法，每一步都要看向未来，要选取与终点距离最小的点，这样容易走入死胡同然后再返回来。
两者结合起来，取长补短，就是我们的astar算法。

ASTAR的变种

beam search

主要是限制了优先队列的数量，避免在垃圾节点上浪费太多时间

Iterative deepening

每一步都向前看，不断迭代最优解
我的理解是，节约空间，但是增加时间

Dynamic weighting

f(p) = g(p) + w(p) * h(p)
其中w(p) >= 1, 越靠近终端，值越小