1 第4章 搜索策略部分参考答案 4 .5 有一农夫带一条狼,一只羊和一框青菜与从河的左岸乘船倒右岸,但受到下列条件的限制: (1) 船太小,农夫每次只能带一样东西过河; (2) 如果没有农夫看管,则狼要吃羊,羊要吃菜。 请设计一个过河方案,使得农夫、浪、羊都能不受损失的过河,画出相应的状态空间图。 题示:(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) 第四步,根据上述定义的状态和操作进行 求 解。 该 问题求 解过程 的状态空间图如下: 2 4 .7 圆盘问题。设有大小不等的三个圆盘A、B、C 套在一根轴上,每个盘上都标有数字1、2、3、4,并且每个圆盘都可以独立的绕轴做逆时针转动,每次转动90°,其初始状态S0和目标状态Sg如图4-...