定理3

    定理3: A^*算法是可采纳的，即如果从初始点到一个目标结点存在一条路径，则A^*算法必然一找到最佳路径结束。

      证明:首先，对于隐含图有限的情况，如果从初始结点s到一个目标结点存在一条路径，则A*算法必将中止与某一目标结点。对于隐含图为无限的情况，根据定理2，如果从初始结点s到一个目结点存在一条路径，则A*算法必然结束。但A*不会因用完OPEN表而结束，这是因为根据引理2-2，在A结束之前，必有一个处在由初始结点s到一个目标结点的最佳路径上的节点在OPEN表中，故A*算法必然中止于某一目标结点。

       其次，假设A*算法终止于某一目标结点t而没有找到最佳路径，则有：

                   f(t)=g(t)＞f(s)

       但根据引理2-2，在算法终止前，必有最佳路径上的一个结点n'在OPEN表中，且有：

                   f(n')≤f*(s)＜f(t)

       这时，A*算法应扩展结点n',而不是结点t，与假设矛盾。[证毕]

    推论3-1：在A*算法中对任何被扩展的结点n，都有f(n)≤f*(s)

　返回