Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。
最佳优先搜索不能保证找到一条最短路径。然而,它比Dijkstra算法快的多,因为它用了一个启发式函数(heuristic function)快速地导向目标结点。
A* 把Dijkstra算法(靠近初始点的结点)和BFS算法(靠近目标点的结点)的信息块结合起来,形成一个评估函数 f(n) = g(n)+h(n)
A*算法有两个集合,OPEN集和CLOSED集。其中OPEN集保存待扩展的结点。CLOSED集保存已扩展过的结点。
开始时,OPEN集只包含一个元素:初始结点。CLOSED集是空的。 在主循环中重复地从OPEN集中取出最好的结点n(评估函数f最小的结点)并检查之:
从图中看出存在相同的大量相同的f(x),open集中选出的最小值不确定
为了解决这个问题,我们可以为启发函数添加一个附加值。附加值对于结点必须是确定性的(也就是说,不能是随机的数),而且它必须让f值体现区别。一种添加附加值的方式是稍微改变h的衡量单位。如果我们减少衡量单位,那么当我们朝着目标移动的时候f将逐渐增加。很不幸,这意味着A倾向于扩展到靠近初始点的结点,而不是靠近目标的结点。我们可以增加衡量单位(甚至是0.1%),A就会倾向于扩展到靠近目标的结点。