1、用回溯策略求解如下所示二阶梵塔问题，画出搜索过程的状态变化示意图。

对每个状态规定的操作顺序为：先搬1柱的盘，放的顺序是先2柱后3柱；再搬2柱的盘，放的顺序是先3柱后1柱；最后搬3柱的盘，放的顺序是先1柱后2柱。




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

其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：
（1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；
（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h(n)是否满足下界范围？在你的搜索树中，对所有的节点满足不满足单调限制？




3、对1.4节中的旅行商问题，定义两个h函数（非零），并给出利用这两个启发函数用算法A求解1.4节中的五城市问题。讨论这两个函数是否都在h*的下界范围及求解结果。




4、2.1节四皇后问题表述中，设应用每一条规则的耗散值均为1，试描述这个问题h*函数的一般特征。你是否认为任何h函数对引导搜索都是有用的？




5、对N＝5，k≤3的M－C问题，定义两个h函数（非零），并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题时是否得到最佳解。




6、证明OPEN表上具有f(n)＜f*(s)的任何节点n，最终都将被A*选择去扩展。




7、如果算法A*从OPEN表中去掉任一节点n，对n有f(n)＞F（F＞f*(s)），试说明为什么算法A*仍然是可采纳的。




8、用算法A逆向求解图2.7中的八数码问题，评价函数仍定义为f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相会。




9、讨论一个h函数在搜索期间可以得到改善的几种方法。




10、四个同心圆盘的扇区数字如图所示，每个圆盘可单独转动。问如何转动圆盘使得八个径向的4个数字和均为12。