定理 5

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

     证明：设A*正要扩展结点n(及结点n处于OPEN表中的第一个时)，而结点序列
P=(s=n0,n1,n2,...,nk=n)是由初始结点s到结点n的最佳路径，其中ni是这个序列中最后一个位于cLOSE表中的结点，则结点序列中的结点ni+1必然在OPEN表中，我们有：

                        g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)
因为结点ni和ni+1都在最佳路径中
                          g*(ni+1)=g*(ni)+c(ni,ni+1)
所以
                          g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)
一直推导下去可得
                           g*(ni+1)+h(ni+1)≤ g*(nk)+h(nk)
由于结点在最佳路径上，故有：
                             f(ni+1)≤g*(n)+h(n)
因为这时A*扩展结点n而不扩展结点ni+1,故必有
                   f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)
故有
                          g(n) ≤g*(n)
但是g*(n)是最小耗散值，应当有
                                g(n)≥g*(n)
所以  
                                 g(n)=g*(n)

  [证毕]
     

                                  返回