ai1

ai1

-

2023年2月10日发(作者：纳西语)

人工智能原理

Homework#1

(搜索问题)

I.水壶问题

考虑以下问题：

"三个水壶里面装有水，水壶上没有任何的测量标记。可以把每个水壶都倒空；也可以把水

从一个水壶倒入到另一个水壶中，当一个倒空或者一个完全装满时，倒水会立即停止。此外，不再允许其他的

动作。三个水壶的容量分别为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。

n双8数码问题

考虑双8数码问题（这是8数码问题的组合，即要求将两个8数码牌经过移动使其布局到达各自的目标状

态）。

a.将双8数码问题进行问题形式化；

b.整个状态空间有多少种状态？可到达的状态又有多少？（给出表达式，不需计算出具体数值）

参考解答：

a.初始状态：两个任意的8数码布局；后继函数：在未解决的8数码棋盘上移动一步；目标测试：两个8

数码棋盘均到达目标状态；路径耗散：每一步为单位耗散。

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

达状态。