人工智能经典习题集及各章总结(期末考试必备) 下载本文

请设计一个过河方案,使得农夫、浪、羊都能不受损失的过河,画出相应的状态空间图。 题示:(1) 用四元组(农夫,狼,羊,菜)表示状态,其中每个元素都为0或1,用0表示在左岸,用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作,每次过河都必须有农夫,因为只有他可以划船。

解:第一步,定义问题的描述形式

用四元组S=(f,w,s,v)表示问题状态,其中,f,w,s和v分别表示农夫,狼,羊和青菜是否在左岸,它们都可以取1或0,取1表示在左岸,取0表示在右岸。

第二步,用所定义的问题状态表示方式,把所有可能的问题状态表示出来,包括问题的初始状态和目标状态。

由于状态变量有4个,每个状态变量都有2种取值,因此有以下16种可能的状态: S0=(1,1,1,1),S1=(1,1,1,0),S2=(1,1,0,1),S3=(1,1,0,0) S4=(1,0,1,1),S5=(1,0,1,0),S6=(1,0,0,1),S7=(1,0,0,0) S8=(0,1,1,1),S9=(0,1,1,0),S10=(0,1,0,1),S11=(0,1,0,0) S12=(0,0,1,1),S13=(0,0,1,0),S14=(0,0,0,1),S15=(0,0,0,0)

其中,状态S3,S6,S7,S8,S9,S12是不合法状态,S0和S15分别是初始状态和目标状态。

第三步,定义操作,即用于状态变换的算符组F

由于每次过河船上都必须有农夫,且除农夫外船上只能载狼,羊和菜中的一种,故算符定义如下:

L(i)表示农夫从左岸将第i样东西送到右岸(i=1表示狼,i=2表示羊,i=3表示菜,i=0表示船上除农夫外不载任何东西)。由于农夫必须在船上,故对农夫的表示省略。

R (i)表示农夫从右岸将第i样东西带到左岸(i=1表示狼,i=2表示羊,i=3表示菜,i=0表示船上除农夫外不载任何东西)。同样,对农夫的表示省略。

这样,所定义的算符组F可以有以下8种算符: L (0),L (1),L (2),L (3) R(0),R(1),R (2),R (3)

第四步,根据上述定义的状态和操作进行求解。 该问题求解过程的状态空间图如下:

(1,1,l,1)

L(2)

(0,1,0,1) R(0) (1,1,0,1)

L(1) L(3)

(0,0,0,1) (0,1,0,0)

R(2) (1,0,1,1)

R(2) (1,1,1,0) L(2)

L(3)

(0,0,1,0) R(0)

(1,0,1,0) L(2) (0,0,0,0)

4.7 圆盘问题。设有大小不等的三个圆盘A、B、C套在一根轴上,每个盘上都标有数字1、2、3、4,并且每个圆盘都可以独立的绕轴做逆时针转动,每次转动90°,其初始状态S0和目标状态Sg如图4-31所示,请用广度优先搜索和深度优先搜索,求出从S0到Sg的路径。

1 2 C 2 C 2 B 4 B A A 2 2 3 3 1 4 1 3 3 3 1 1 1 2 4 4 4 3 4 初始状态S0 目标状态Sg

图 4-31 圆盘问题

解:设用qA,qB和qC分别表示把A盘,B盘和C盘绕轴逆时针转动90o,这些操作(算符)的排列顺序是qA,qB,qC。

应用广度优先搜索,可得到如下搜索树。在该搜索树中,重复出现的状态不再划出,节点旁边的标识Si,i=0,1,2,…,为按节点被扩展的顺序给出的该节点的状态标识。

由该图可以看出,从初始状态S0到目标状态Sg的路径是 S0→2→5→13(Sg)

qA 2 S1 2 1 3 3 24 11 3 4 4 qB 2 S0 C 2 B 2 A 3 3 1 1 1 3 4 4 4 2 1 2 4 3 4 qC S3 1 2 2 2 3 3 1 1 4 4 4 3 S2 3 2 3 qC 1 4 1 qA qB 2 1 S4 S5 2 S6 22 1 1 1 3 3 1 4 3 1 1 3 2 2 4 4 1 23 24 14 3 1 3 2 3 3 4 3 4 4 3 4 qA 2 2 3 qB S10 2 4 2 4 2 4 S7 1 3 1 2 2 3 1 1 2 4 3 3 S8 1 4 4 qC qC 2 1 4 S11 1 S12即Sg 2 4 3 3 4 3 2 1 1 3 2 1 2 1 3 1 4 3 4 1 1 2 2 4 4 3 3 4 4 4.7题的广度优先搜索树

S9 4 2 2 1 3 3 1 1 3 4 4 2

其深度优先搜索略。

4.8 图4-32是5个城市的交通图,城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发,经过其它各城市一次且仅一次,最后回到A城,请找出一条最优线路。

解:这个问题又称为旅行商问题(travelling A 10 B salesman problem, TSP)或货郎担问题,是一个 2 8 较有普遍性的实际应用问题。根据数学理论, 9 C 11 6 对n个城市的旅行商问题,其封闭路径的排列 3 12 8 D 9 E 总数为:

(n!)/n=(n-1)! 4-32 交通费用图 其计算量相当大。例如,当n=20时,要穷举其

所有路径,即使用一个每秒一亿次的计算机来算也需要350年的时间。因此,对这类问题只能用搜索的方法来解决。

下图是对图4-32按最小代价搜索所得到的搜索树,树中的节点为城市名称,节点边上的数字为该节点的代价g。其计算公式为

g(ni+1)=g(ni)+c(ni, ni+1)

其中,c(ni,ni+1)为节点ni到ni+1节点的边代价。 0

A 10 2 11 9 11 B 10 C 2 D 9 E

8 12 6 8 3 8 12 3 9 6 8 9 18 16 20 C 18 D 22 E B 10 D 5 E 10 B 21 C 12 E C 19 D B 17

3 9 8 8 8 12 3 12 6 6 9 12 3 8 8 6 8 12 6 8 9 3 8 9 23 31 29 25 22 16 19 20 20 C 25 D B 32 C C E 16 B E D D B E

22

21 24 14 26 B 24 27 25 17 D E 26 20 27 C D B E C C E B D 8 8 9 9 12 12 3 6 6

8 6 6 12 8 9 9 3 3 31 27 28 31 26 31 E 33 E D D B E 26 B 28 B D

34 32 B 30 23 20 C E D 27 C 28 E B E 28 D 35

10 2

A 30 30 A

图4.32的最小代价搜索树

可以看出,其最短路经是 A-C-D-E-B-A 或

A-B-E-D-C-A

其实,它们是同一条路经。

4.11 设有如下结构的移动将牌游戏:

B B W W E 其中,B表示黑色将牌,W表是白色将牌,E表示空格。游戏的规定走法是:

(1) 任意一个将牌可移入相邻的空格,规定其代价为1;

(2) 任何一个将牌可相隔1个其它的将牌跳入空格,其代价为跳过将牌的数目加1。 游戏要达到的目标什是把所有W都移到B的左边。对这个问题,请定义一个启发函数h(n),并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下解要求?再求出的搜索树中,对所有节点是否满足单调限制?

解:设h(x)=每个W左边的B的个数,f(x)=d(x)+3*h(x),其搜索树如下: f(x)=0+12=12 B B W W E f(x)=1+12=13 f(x)=1+12=13 B B E W W B B W E W f(x)=2+12=14 f(x)=2+9=11 B B E W W B E W B W f(x)=3+9=12