定理6

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

证明：假设结点n₂在结点n₁之后立即被扩展，这时有两种情况：

     （1）扩展结点n1是结点n2在OPEN表上，则显然有f(n₁)≤f(n₂)。

     （2）扩展结点n1是结点n₂不在OPEN表上，则扩展结点n₁时必然把结点n₂加到OPEN表中，即结点n₂是结点n₁的一个后继结点。在扩展结点n₁时有
                             f(n₂)=g(n₂)+h(n₂)
由定理5 可知
                             g(n₂)=g*(n₂)
因此
                        f(n₂)=g*(n₂)+h(n₂)
                             =g*(n₁)+c(n₁,n₂)+h(n₂)
                             =g(n₁)+c(n₁,n₂)+h(n₂)
由于单调限制
                              c(n₁,n₂)+h(n₂)≥h(n₁)
所以有:
                           f(n₂)≥g(n₁)+h(n₁)=f(n₁)

[证毕]

                                                                        返回