您好,欢迎来到爱问旅游网。
搜索
您的当前位置:首页人工智能(考点复习整理)

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

来源:爱问旅游网
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] (将某一壶里的水倒空)

- [xmin(x+y,7)+y, min(x+y,7), z] (将 x 倒入 y)

- [x, ymin(y+z,3)+z, min(y+z,3)] (将 y倒入z)

- [min(x+z,15), y, zmin(x+z,15)+x] (将 z倒入x)

- [xmin(x+z,3)+z, y, min(x+z,3)] (将 x倒入 z)

- [min(x+y,15), ymin(x+y,15)+x, z] (将 y倒入x)

- [x, min(y+z,7), zmin(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*算法解决下图所示八数码问题。

参考解答:

Ⅱ. 某问题的状态空间图如下图所示,其中括号内标明的是各节点的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. h0:SBCG

h1:SBCG

h2:SBDG

Homework #4

(约束满足问题)

Ⅰ. 你负责安排计科专业的课程的授课教师,课程安排在星期一、星期三和星期五。计科专业共有5个班,邀请校外3位资深教授来讲授课程。你需要确定哪个班级由哪位教授上课,你的安排计划要满足以下约束:同一时刻每个教授只能上(12分)

1

个班的课。

具体的班级课程对应关系如下:

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在图上标出应用剪枝算法不会访问到的结点(假设子结点的访问顺序为从左至右)。

参考解答:

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- awee.cn 版权所有 湘ICP备2023022495号-5

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务