1.几个记号
    令k(ni,nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点,函数k没有定义)。于是,从节点n到某个具体的目标节点ti,某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合{ti}上所有k(n,ti)中最小的一个,因此,h*(n)就是从n到目标节点最小代价路径的代价,而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n,函数h*没有定义)。

本文来自www.eadianqi.com

2.估价函数的定义
    定义g*为g*(n)=k(S,n)
    定义函数f*,使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和,即
        f*(n)=g*(n)+h*(n)
    希望估价函数f是f*的一个估计,此估计可由下式给出:
        f(n)=g(n)+h(n)
    其中:g是g*的估计;h是h*的估计。对于g(n)来说,一个明显的选择就是搜索树中从S到n这段路径的代价,这一代价可以由从n到S寻找指针时,把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)≥g*(n)。h*(n)的估计h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数。

自动控制网www.eadianqi.com版权所有

3.A*算法定义
    定义1  在GRAPHSEARCH过程中,如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的,则称该过程为A算法。
    定义2  在A算法中,如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界,它表示某种偏于保守的估计。
    定义3  采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。当h=0时,A*算法就变为有序搜索算法。