人工智能(考点复习整理)

1、Homework #1(搜索问题)I.水壶问题考虑以下问题：“三个水壶里面装有水，水壶上没有任何的测量标记。可以把每个水壶都倒空；也可以把水 从一个水壶倒入到另一个水壶中，当一个倒空或者一个完全装满时，倒水会立即停止。此外，不 再允许其他的动作。三个水壶的容量分别为15, 7和3升。需要量出正好2升水。”将以上问题表达为一个搜索问题，即给出(1)状态的描述，(2)初始状态，(3)目标测试， 及(4)后继函数。说明：不要列出所有的状态；对于后继函数，不需要把每个状态的所有后继都列出来，但是应 该描述清楚针对给定的任意状态如何得到其后继。此处不要求对问题的解进行描述。 画出上述搜索问题的搜索树，画

2、到深度为2即可(根节点深度为0)。在深度为0时分支因子是多少？深度为1时分支因子又是多少？参考解答：(1)状态描述：氐y, z,其中x, y, z分别为3个水壶中水的重量(整数)。初始状态：15, 7, 3.目标测试：对状态x, y, z,有 x=2, or y=2, or z=2后继函数：给定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-m

3、in(x+z,15)+x(将z 倒入 x)-x-min(x+z,3)+z, y, min(x+z,3)(将工倒入 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)搜索树根节点：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,015,0,3 = 0,0,3, 15,0,0, 8,7,3, 15,3,015,

4、7,0 = 0,7,0, 15,0,0, 12,7,3, 15,4,3深度为0时分支因子为3,深度为1时分支因子为4。II双8数码问题考虑双8数码问题（这是8数码问题的组合，即要求将两个8数码牌经过移动使其布局到达各自的目标 状态）。将双8数码问题进行问题形式化；整个状态空间有多少种状态？可到达的状态又有多少？（给出表达式，不需计算出具体 数值）参考解答：初始状态：两个任意的8数码布局；后继函数：在未解决的8数码棋盘上移动一步；目标测试：两 个8数码棋盘均到达目标状态；路径耗散：每一步为单位耗散。每一个8数码问题有9!个状态，其中一半是可达的；则两个8数码问题联合起来有（9!） 2/2 个可达

5、状态。Homework #2（盲目搜索）1考虑这样一个状态空间，每一个状态是一个不同的正整数，即为集合1,2,3 中的一个元素。后继函数为：状态n返回两种状态：数字2n和2n 1 ；初始状态为1。（12分）画出包含状态1至15状态的状态图。令目标状态为11。搜索算法在生成了搜索树的一个节点，该节点的状态为n时，访问状态n。 分别列出以下搜索算法的访问次序。a）广度优先搜索b）深度限制搜索（限制深度为3）c）迭代深入搜索参考解答：a.b. a) BFS: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11DFS: 1, 2, 3, 4, 5, 8, 9, 10, 11IDS: 1

6、; 1, 2, 3; 1, 2, 3, 4, 5, 6, 7; 1, 2, 3, 4, 5, 8, 9, 10, 11II简述广度优先搜索、深度优先搜索、迭代深入搜索的基本原理，及其算法性能分析。参考解答：自己对照课本及课件理解自行总结。Homework #3（启发搜索）I用A*算法解决下图所示八数码问题。s*参考解答:CgUlP=5 f=516 475A2 8 316 47 5P=6f=7-2 8 3147 6 5E irD2 8 3P=4f=52 8 316 47 5F147 0 5P=5f=7P=Sf=7条 318 47 6 5P=3f=5G2 318 47 6 5P=2f=5H 丁厂

7、18 4 7 6 5P=5f=7P=4f=712 3.8 47 6 5h：+=L 的4P=1f=51 ；2 3, v 3= -12 3.8.4P=07 8 47 6 5f=56 5P=2f=7II.某问题的状态空间图如下图所示，其中括号内标明的是各节点的h值，弧线边的数字是该弧线的 耗散值，试用A算法求解从初始节点S到目标节点T的路径。要求给出搜索图，标明各节点的f值， 及各节点的扩展次序，并给出求得的解路径。参考解答：搜索图如下页图所示，其中括号内标出的是节点的f值，圆圈内的数字是扩展的次序。 得到的解路径为：S-B-F-J-T。附加题：考虑下图所示搜索问题5Node/圮hiS0.56A03

8、.5B042C09 m3.5D0.53G000a.对于表中所列出的3个启发函数，哪（几）个是可纳的？请做简要分析。b.分别使用上述三个启发函数，进行A*搜索，请分别给出它们返回的解路径。h0：hi:h2：参考解答：h。和是可纳的，因为h2（C）h*（C）,所以h2不是可纳的。h: S B C Gh1: S B C Gh2: S T B T D T GHomework #4（约束满足问题）I你负责安排计科专业的课程的授课教师，课程安排在星期一、星期三和星期五。计科专业共有5个班，邀请校外3位资深教授来讲授课程。你需要确定哪个班级由哪位教授上课，你的安排计划要满足 以下约束：同一时刻每个教授只能上

9、 1 个班的课。（12 分）具体的班级课程对应关系如下：1班：程序设计（上午8:00-9:00）2班：人工智能（上午8:30-9:30）3班：自然语言处理（上午9:00-10:00）4班：计算机视觉（上午9:00-10:00）5班：机器学习（上午9： 30-10： 30）资深教授具体讲授课程如下：A教授可以上3和4班的课B教授可以上2、3、4和5班的课C教授可以上1、2、3、4和5班的课a.将上述问题形式化为CSP问题，每个班作为一个变量，进行满足约束关系的赋值（注：形式化不需 要给出具体的赋值）。变量及其值域：C1C2C3C4C5约束关系：CB,CA,B,CA,B,CB,CC1 丰 C2,

10、C2 丰 C3, C3 丰 C4, C4 丰 C5, C2 丰 C4, C3 丰 C5.b.根据你形式化的CSP问题，画出相应的约束图。根据约束图应用弧约束关系后，各变量的值域将发生变化，请写出应用约束关系后的值域。值域变化如下：C1 CC2 BC3 A,CC4 A,CC5 B,C给出该CSP问题的一个解。C1 = C, C2 = B, C3 = C, C4 = A, C5 = B 是问题的一个解。e简述约束满足问题形式化的过程步骤?Homework #5（对抗搜索和博弈）1下图所示博弈树，按从左到右的顺序进行a-p剪枝搜索，试标明各生成节点的回推值，何处发生 剪枝，及应选择的走步。参考解答:

11、II.下图所示博弈树，按从左到右的顺序进行a-p剪枝搜索，试标明各生成节点的回推值，何处发生 剪枝，及应选择的走步。5 -5 U 1 5 10 -1 -2 0 14 5-1oI5 -3 3 3 -3 0 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 3 -3 0 l-2 0 1 4 5 1-1-1 3 -3 20 QtJ口口口 附加题：考虑下图所示的极大极小树:请用X在图上标出应用a - p剪枝算法不会访问到的结点（假设子结点的访问顺序为从左至右）。参考解答:S. (15 pdints.) Game Trees: The BalancerConsider ihp

12、 following zero-sum game, in which Lhe utilities L侦(s arc shown for the first payer (A). Assume the second player (R) is a mmirniaer: E hoDdi the opposite utiUitis to A? = -L侦(幻一 In this rase一 l!s mALniizaLion of Ue 也(xjuivalenL to miniiniatLon of Ua : Le. the compuLation in Btndard minima.(a) (2 po

13、ints) In each node, write【侦时.lh (minimax) utility of that stAtc for player A,畋umifig that H is a minimizer.Ansviier: Displayed Abdve,(b) (3 points) Crass off any nodes which will be skipped bypruning.心unilng left-to-right ardrine.Aitsvrer: Displayed Abdve,Assume now thL R in not & inininiLzer. bul 角 baianccr. A balancer does not iry to HiLnimiz A 近 scor bui