人工智能_(马少平_朱小燕_著)_清华大学出版社_课(8)

2、滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：

其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是： （1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；

（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数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；