算法示例

     设某个问题的状态空间如图2．11所示，其中n_o为初始结点，n₇、n₈为终结点，且每个
k－1连接符的耗散值为k。我们选取启发函数h(n)如下：

                    h(n₀)=0，             h(n₁)=2，               h(n₂)=4

                     h(n₃)=4，             h(n₄)=1，               h(n₅)=1

                     h(n₆)=2，             h(n₇)=0，               h(n₈)=0

    注意，上述函数h(n)为h*(n)的一个下界，且满足单调限制。搜索过程由4个外循环组成，如图2-13所示。图中用箭头标记连接符，用空心圆表示未标记SOLVED的结点，用实心圆表示已标记SOLVED的结点，结点的耗散值标在结点旁边。第4个外循环结束后，根据标记的连接符就可以找到一个解图，该解图为具有最小耗散值的解图。

    可以证明，如果从一初始点到一组终结点存在一个解图，且h(n)是h*(n)的一个下界，h(n)满足单调限制，则AQ*算法将终止于一个最佳解图。

                                                                   返回