人工智能(考点复习整理) .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状态的状态图。