游戏要达到的目标是使所有白将牌都处在黑将牌的左边(左边有无空格均可)。对这个问题,定义一个启发函数h(n),并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h(n)是否满足下界范围?在你的搜索树中,对所有的节点满足不满足单调限制?Р 提示:可定义h为:Рh=B右边的W的数目Р设j节点是i节点的子节点,则根据走法不同,h(i)-h(j)的值和C(i, j)分为如下几种情况:Р(1)B或W走到了相邻的一个空格位置,此时: h(i)-h(j)=0, C(i,j)=1;Р(2)W跳过了1或2个W,此时 h(i)-h(j)=0, C(i,j)=1或2; Р(3)W向右跳过了一个B(可能同时包含一个W),此时: h(i)-h(j)=-1, C(i,j)=1或2;Р(4)W向右跳过了两个B,此时: h(i)-h(j)=-2, C(i,j)=2; Р(5)W向左跳过了一个B(可能同时包含一个W),此时: h(i)-h(j)=1, C(i,j)=1或2; Р(6)W向左跳过了两个B,此时: h(i)-h(j)=2, C(i,j)=2; Р(7)B跳过了1或2个B,此时 h(i)-h(j)=0, C(i,j)=1或2; Р(8)B向右跳过了一个W(可能同时包含一个B),此时: h(i)-h(j)=1, C(i,j)=1或2;Р(9)B向右跳过了两个W,此时: h(i)-h(j)=2, C(i,j)=2;Р(10)B向左跳过了一个W(可能同时包含一个B),此时: h(i)-h(j)=-1, C(i,j)=1或2; Р(11)B向左跳过了两个W,此时: h(i)-h(j)=-2, C(i,j)=2;Р纵上所述,无论是哪一种情况,具有:Рh(i)-h(j)≤C(i,j)Р且容易验证h(t)=0,所以该h是单调的。由于h满足单调条件,所以也一定有h(n)≤h*(n),即满足A*条件。
全文预览
