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

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,ory=2,orz=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(盲目搜索)Ⅰ.考虑这样一个状态空间，每一个状态是一个不同的正整数，即为集合}3,2,1{中的一个元素。后继函数为：状态n返回两种状态：数字n2和12n；初始状态为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,11b)DFS:1,2,3,4,5,8,9,10,11c)IDS:1;1,2,3;1,2,3,4,5,6,7;1,2,3,4,5,8,9,10,11Ⅱ.简述广度优先搜索、深度优先搜索、迭代深入搜索的基本原理，及其算法性能分析。参考解答：自己对照课本及课件理解自行总结。Homework#3(启发搜索)Ⅰ.用A*算法解决下图所示八数码问题。参考解答：Ⅱ.某问题的状态空间图如下图所示，其中括号内标明的是各节点的h值，弧线边的数字是该弧线的耗散值，试用A算法求解从初始节点S到目标节点T的路径。要求给出搜索图，标明各节点的f值，及各节点的扩展次序，并给出求得的解路径。参考解答：搜索图如下页图所示，其中括号内标出的是节点的f值，圆圈内的数字是扩展的次序。得到的解路径为：S-B-F-J-T。附加题：考虑下图所示搜索问题a.对于表中所列出的3个启发函数，哪（几）个是可纳的？请做简要分析。b.分别使用上述三个启发函数，进行A*搜索，请分别给出它们返回的解路径。h0:h1:h2:参考解答：a.h0和h1是可纳的，因为h2(C)h*(C),所以h2不是可纳的。b.GCBSh:0GCBSh:1GDBSh:2Homework#4(约束满足问题)Ⅰ.你负责安排计科专业的课程的授课教师，课程安排在星期一、星期三和星期五。计科专业共有5个班，邀请校外3位资深教授来讲授课程。你需要确定哪个班级由哪位教授上课，你的安排计划要满足以下约束：同一时刻每个教授只能上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问题，每个班作为一个变量，进行满足约束关系的赋值（注：形式化不需要给出具体的赋值）。变量及其值域：C1{C}C2{B,C}C3{A,B,C}C4{A,B,C}C5{B,C}约束关系：C1C2,C2C3,C3C4,C4C5,C2C4,C3C5.b.根据你形式化的CSP问题，画出相应的约束图。c.根据约束图应用弧约束关系后，各变量的值域将发生变化，请写出应用约束关系后的值域。值域变化如下：C1{C}C2{B}C3{A,C}C4{A,C}C5{B,C}d.给出该CSP问题的一个解。C1=C,C2=B,C3=C,C4=A,C5=B是问题的一个解。e简述约束满足问题形式化的过程步骤？Homework#5(对抗搜索和博弈)Ⅰ.下图所示博弈树，按从左到右的顺序进行α-β剪枝搜索，试标明各生成节点的回推值，何处发生剪枝，及应选择的走步。参考解答：Ⅱ.下图所示博弈树，按从左到右的顺序进行α-β剪枝搜索，试标明各生成节点的回推值，何处发生剪枝，及应选择的走步。附加题：考虑下图所示的极大极小树：请用X在图上标出应用剪枝算法不会访问到的结点（假设子结点的访问顺序为从左至右）。参考解答：