定理4

定理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扩展得结点少。

证明:对A2搜索树中结束处的结点深度应用归纳法。

     (1)对A2搜索树中d(n)=0的结点n，因为结点n为初始结点，如果n为目标结点，则两种算法都不扩展n。如果n不是目标结点，则两种算法都要扩展n。

     (2) 设对A2搜索树中d(n)=k的任意结点n，结论成立，即A1也扩展了这些结点。

     (3)证明A2搜索树中d(n)=k+1的任意结点n，也要由A1扩展。

      应用反证法，假设A2搜索树上有一个满足d(n)=k+1的结点n,A2扩展了该结点，但A1没有扩展它。根据第2条的假设，知道A1扩展了结点n的父结点，因此n必定在A1的OPEN表中，既然结点n没有被A1扩展，因此有
                       f1(n)≥f*(s)
即
                  g1(n)+h1(n)≥f*(s)                                      (1)
但由于d=k时，A2扩展的结点A1也一定扩展，故有
                       g1(n)≤g2(n)                                       (2)
因此有
                     h1(n)≥f*(s)-q2(n)                                   (3)
另一方面，由于A2扩展了n,因此有
                      f2(n)≤f*(n)
即
                g2(n)+g2(n)≤f*(s)
所以
                h2(n)≤f*(s)-g2(n)
由式(3),(4)可知
                h1(n)≥h2(n)
上式与定理的前提条件矛盾，因此反证法的假设不成立。

[证毕]   

　                            返回