图2.6 搜索示意图 f(m1)=g(m1)+h(m1) f(n，m2)=g(n，m2)+h(m2) f(n，m3)=g(n，m3)+h(m3)
然后按第6步条件进行指针设置和第7步重排OPEN表节点顺序，以便确定下一次要扩展的节点。
用A算法来求解一个问题，最主要的就是要定义启发函数h(n)。对于8数码问题，一种简单的启发函数的定义是： h(n) ＝ 不在位的将牌数
什么是\不在位的将牌数\呢？我们来看下面的两个图。
其中左边的图是8数码问题的一个初始状态，右边的图是8数码问题的目标状态。我们拿初始状态和目标状态相比较，看初始状态的哪些将牌不在目标状态的位置上，这些将牌的数目之和，就是\不在位的将牌数\。比较上面两个图，发现1、2、6和8四个将牌不在目标状态的位置上，所以初始状态的\不在位的将牌数\就是4，也就是初始状态的h值。其他状态的h值，也按照此方法计算。
下面再以八数码问题为例说明好的优先搜索策略的应用过程。设评价函数f(n)形式如下： f(n)=d(n)+W(n)
其中d(n)代表节点的深度，取g(n)=d(n)表示讨论单位耗散的情况；取h(n)=W(n)表示\不在位\的将牌个数作为启发函数的度量，这时f(n)可估计出通向目标节点的希望程度。图2.7表示使用这种评价函数时的搜索树，图中括弧中的数字表示该节点的评价函数值f。算法每一循环结束时，其OPEN表和CLOSED表的排列如下：
根据目标节点L返回到s的指针，可得解路径S(4)，B(5)，E(5)，I(5)，K(5)，L(5)
图2.7给出的是使用A算法求解8数码问题的搜索图。其中A、B、C等符号，只是为了标记节点的名称，没有特殊意义。这些符号旁边括弧中的数字是该节点的评价函数值f。而圆圈中的值，则表示节点的扩展顺序。
从图中可以看出，在第二步选择节点B扩展之后，OPEN表中f值最小的节点有D和E两个节点，他们的f值都是5。在出现相同的f值时，A算法并没有规定首先扩展哪个节点，可以任意选择其中的一个节
点首先扩展。
图2.7 八数码问题的搜索树
相关推荐：
loading