Homework #1
(搜索问题)
Ⅰ. 水壶问题
考虑以下问题:
“三个水壶里面装有水，水壶上没有任何的测量标记。可以把每个水壶都倒空；也可以把水从一个水壶倒入到另一个水壶中，当一个倒空或者一个完全装满时，倒水会立即停止。此外，不再允许其他的动作。三个水壶的容量分别为15，7和3升。需要量出正好2升水。”
1． 将以上问题表达为一个搜索问题，即给出（1）状态的描述，（2）初始状态，（3）目标测试，
及（4）后继函数。
[说明：不要列出所有的状态；对于后继函数，不需要把每个状态的所有后继都列出来，但是应该描述清楚针对给定的任意状态如何得到其后继。此处不要求对问题的解进行描述。]
2． 画出上述搜索问题的搜索树，画到深度为2即可（根节点深度为0）。在深度为0时分支因子
是多少？深度为1时分支因子又是多少？ 参考解答： 1.
(1) 状态描述： [x, y, z], 其中 x, y, z 分别为3个水壶中水的重量（整数）。 (2) 初始状态： [15, 7, 3].
(3) 目标测试：对状态 [x, y, z], 有x=2, or y=2, or z=2 (4) 后继函数：给定 [x, y, z], 生成以下：
- [0, y, z], [x, 0, z], and [x, y, 0] (将某一壶里的水倒空) - [x?min(x+y,7)+y, min(x+y,7), z] (将 x 倒入 y) - [x, y?min(y+z,3)+z, min(y+z,3)] (将 y倒入z) - [min(x+z,15), y, z?min(x+z,15)+x] (将 z倒入x) - [x?min(x+z,3)+z, y, min(x+z,3)] (将 x倒入 z) - [min(x+y,15), y?min(x+y,15)+x, z] (将 y倒入x) - [x, min(y+z,7), z?min(y+z,7)+y] (将 z倒入y)
2.
搜索树根节点： [15,7,3]
深度1的节点： [0,7,3], [15,0,3], [15,7,0] (因为所有的水壶在初始时均装满了水，所以在唯一可能的动作是将壶里的水倒空) 深度2的节点：
[0,7,3] => [0,0,3], [0,7,0], [7,0,3], [3,7,0] [15,0,3] => [0,0,3], [15,0,0], [8,7,3], [15,3,0] [15,7,0] => [0,7,0], [15,0,0], [12,7,3], [15,4,3]
深度为0时分支因子为3，深度为1时分支因子为4。
Ⅱ 双8数码问题
考虑双8数码问题（这是8数码问题的组合，即要求将两个8数码牌经过移动使其布局到达各自的目标状态）。
a. 将双8数码问题进行问题形式化；
b. 整个状态空间有多少种状态？可到达的状态又有多少？（给出表达式，不需计算出具体
数值）
参考解答：
a. 初始状态：两个任意的8数码布局；后继函数：在未解决的8数码棋盘上移动一步；目标测试：两个8数码棋盘均到达目标状态；路径耗散：每一步为单位耗散。
b. 每一个8数码问题有9！个状态，其中一半是可达的；则两个8数码问题联合起来有（9！）/2个可达状态。
2
Homework #2
(盲目搜索)
Ⅰ. 考虑这样一个状态空间，每一个状态是一个不同的正整数，即为集合{1,2,3?}中的一个元素。后
继函数为：状态n返回两种状态：数字2n和2n?1；初始状态为1。 (12分) a. 画出包含状态1至15状态的状态图。
b. 令目标状态为11。搜索算法在生成了搜索树的一个节点，该节点的状态为n时，访问状态n。分别列出以下搜索算法的访问次序。 a) 广度优先搜索
b) 深度限制搜索（限制深度为3）
c) 迭代深入搜索
参考解答：a.
b. a) BFS: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
b) DFS: 1, 2, 3, 4, 5, 8, 9, 10, 11 c) IDS: 1; 1, 2, 3; 1, 2, 3, 4, 5, 6, 7; 1, 2, 3, 4, 5, 8, 9, 10, 11
Ⅱ. 简述广度优先搜索、深度优先搜索、迭代深入搜索的基本原理，及其算法性能分析。
参考解答：自己对照课本及课件理解自行总结。
Homework #3
(启发搜索)
Ⅰ. 用A算法解决下图所示八数码问题。
*
参考解答：
人工智能(考点复习整理)
