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

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数码棋盘均到达目标状态；路径耗散：每一步为单位耗散。

2

b.每一个8数码问题有9！个状态，其中一半是可达的；则两个8数码问题联合起来有（9！）/2

个可达状态。

Homework#2

(盲目搜索)

Ⅰ.考虑这样一个状态空间，每一个状态是一个不同的正整数，即为集合{1,2,3}中的一个元素。后

n2n2n1

继函数为：状态返回两种状态：数字和；初始状态为1。(12分)

a.画出包含状态1至15状态的状态图。