zhuye

最佳路径的图搜索(二)

    三、A*算法信息量的比较

      启发式函数h(n)对A*算法的效率起着重要的影响。

定理4：设两个A*算法A1和A2，他们有

A1:f1(n)=g1(n)+h1(n)

A2:f2(n)=g2(n)+h2(n)

如果A1和A2有更多的信息（及对所有得结点n），都有h1(n)≤h2(n)，则他们对任何存在的一条从初始结点到一个目标结点的路径的图搜索结束时，被A2扩展得结点也必然被A1扩展，即A1扩展得结点不会比A2扩展得结点少。

四、单调限制

定义：如果对所有得结点ni和他的一个后继结点nj，有

0≤h(ni)-h(nj)≤c(ni,nj)

其中h(t)=0(t为任一目标结点)，则称h满足单调限制。

定理5：如果h满足单调条件，则当A*算法扩展结点n时，该结点就已经找到了通往它的最佳路径，即g(n)=g*(n).

定理6：如果h满足单调限制，则A*算法扩展到的结点序列的f值是非递减的。