练习题
1．给出如下问题的形式化（包括状态空间，动作空间，初始状态，转移函数，代价函数，目标测试函数）：
（1）使用四种颜色给一个平面地图着色，要求每两个相邻的地区不能使用同一种颜色；
（2）假设你有一个3升的容器和一个5升的容器（以及充足的水源），仅利用这两个容器精确地量出4升水；
（3）在国际象棋8×8的棋盘上放置八个皇后，要求每行、每列、每个斜线上只能有一个皇后；
（4）农夫需要把狼、羊、菜和自己运到河对岸去。只有农夫能够划船，且除农夫之外每次只能运一种东西；同时如果没有农夫看着，羊会吃菜，狼会吃羊。寻找一种方法，让农夫能够安全过河。
2．考虑桌子上放置的三个小方块，我们允许三种操作：a）将一个上层木块放到桌子上；b）将桌子上的木块放到其他单个木块上；c）将一个上层木块放到其他单个木块上。并且我们只允许移动木块到相邻的地方，如下图所示。我们希望从如下初始状态到达最终状态，画出深度优先搜索树和宽度优先搜索树，并标出搜索顺序。哪一种搜索方法更适合这个问题？
3．考虑显示在下图右边的状态空间图。起始节点是A，目标节点是G。每条边的代价显示在下面的图中，每条边都是双向的。下面的表格中包含三个启发函数h1，h2和h3。
（1）启发函数h1是单调的吗？启发函数h2是单调的吗？为什么？（2）深度优先搜索返回的路径是什么？
（3）宽度优先搜索返回的路径是什么？
（4）贪婪搜索用启发函数h1返回的路径是什么？
（5）贪婪搜索用启发函数h2返回的路径是什么？
（6）A*搜索用启发函数h1返回的路径是什么？
（7）A*搜索用启发函数h2返回的路径是什么？
（8）怎么设置h3（B）的值可以使得启发函数h3成为单调的？
（9）怎么设置h3（B）的值使得A*算法使用启发函数h3扩展节点A，然后C，B和D？
4．考虑显示在下面的零和博弈树。指向上的三角代表MAX玩家的选择（比如根节点），指向下的三角代表MIN玩家的选择。
（1）假设两个玩家使用最优策略，填写每个节点的收益值。
（2）如果使用Alpha-Beta剪枝搜索，哪些节点会被剪掉？如果没有节点被剪枝，说明为什么。假设搜索是从左到右；当选择访问哪个子节点时，先选最左边没有被访问的子节点。
5．“汉诺塔”来源于印度的一个古老传说。汉诺塔由若干个大小不等的圆碟和三根柱子组成，玩法是将所有的圆碟从一根柱子转移到另一根柱子上，但无论任何时刻同一根柱子上较小的圆碟必须处于较大的圆碟上方。对于如下所示二阶（即有A和B两个圆碟的）汉诺塔问题，请用深度优先搜索进行求解，并画出搜索过程的状态变化示意图。
进行搜索的优先级如下：先尝试移动第一根柱子上的圆碟，并尽可能放到第二根柱子上，若不行就尝试放在第三根柱子上；如果不能移动第一根柱子上的圆碟就尝试移动第二根柱子上的圆碟，尽可能放在第三根柱子上，若不行就尝试放在第一根柱子上；如果还是不行就移动第三根柱子上的圆碟，尽可能放在第一根柱子上，若不行就放在第二根柱子上。
6．现在有一个放有若干个小木块的木盘：
如图所示，有三个蓝色木块，两个红色木块，最右侧有一个空出的格子。游戏的规定是：
（1）可以将一个木块移入相邻的空格，需要付出3的代价；
（2）可以将一个木块跨过一个或两个木块移入空格中，需要付出（跨过木块的数目+4）的代价。
将所有的红色木块移动到蓝色木块的左侧，同时空格处于最左侧或者最右侧游戏结束。对这个问题，定义一个启发函数h（n），并利用A*算法进行求解，画出所产生的搜索树。你的启发函数是否满足下界范围？画出的搜索树中，有没有不满足单调限制的节点？
7．对下图所示的博弈树进行α-β搜索，我们规定优先生成左边节点。请在图中标记发生剪枝的位置。
8．现有如下图的转盘，每个圆盘都可以单独转动。如何转动转盘，使得每个径向上的四个数字和均为10？
9．现有4×3的方格，用1，1，1，2，2，2，5，5，6，6，9，9这12个数字填入方格中，使得每行数字组成的十进制数的平方根为整数。找出可以利用的启发信息，设计启发函数，并利用启发式搜索算法求解，分析搜索空间的大小，给出搜索简图。
10．证明如下命题：在执行A*算法时，优先队列表中任何满足f（n）小于最优解的总损耗的节点n，最终都将被拓展。
11．证明在A*算法中，当启发函数具有单调性时，每一个节点只会进入优先队列表一次。
12．两个海盗决定玩一个游戏：两个人从10个金币中轮流拿走一个或两个金币，拿走最后一个金币者算赢。试通过博弈证明，先拿的人必胜，并简要说明取胜策略。
13．编程实现深度优先搜索与宽度优先搜索，以找到一个V=10的节点。分别尝试使用这两种方法解决下图1.15（a）和（b）中的两个问题，两种搜索方式在找到目标之前分别访问了多少个节点？
提示：在实现两种算法时，需要规定访问子节点的顺序。该问题中规定：在遇到多个子节点时，优先访问最左侧未被访问过的节点。
图1.15 两棵待搜索的树，目的是找到一个V=10的节点