A*

Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。

最佳优先搜索不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristic function）快速地导向目标结点。

A* 把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来，形成一个评估函数 f(n) = g(n)+h(n)

A* 的算法流程。

A*算法有两个集合，OPEN集和CLOSED集。其中OPEN集保存待扩展的结点。CLOSED集保存已扩展过的结点。

开始时，OPEN集只包含一个元素：初始结点。CLOSED集是空的。 在主循环中重复地从OPEN集中取出最好的结点n（评估函数f最小的结点）并检查之：

• 如果n是目标结点，则我们的任务完成了。
• 结点n被从OPEN集中删除并加入CLOSED集。然后检查它的邻居n':
  • 如果邻居n'在CLOSED集中，那么它是已经被检查过的，所以我们不需要考虑它；
  • 如果n'在OPEN集中，那么它是以后肯定会被检查的，所以我们现在不考虑它;
  • 否则，n’加入OPEN集，把它的父结点设为n。到达n’的路径的代价g(n’)。

A* 进一步优化

从图中看出存在相同的大量相同的f(x)，open集中选出的最小值不确定

添加附加值优化

为了解决这个问题，我们可以为启发函数添加一个附加值。附加值对于结点必须是确定性的（也就是说，不能是随机的数），而且它必须让f值体现区别。一种添加附加值的方式是稍微改变h的衡量单位。如果我们减少衡量单位，那么当我们朝着目标移动的时候f将逐渐增加。很不幸，这意味着A倾向于扩展到靠近初始点的结点，而不是靠近目标的结点。我们可以增加衡量单位（甚至是0.1%），A就会倾向于扩展到靠近目标的结点。

向量叉乘优化