有一个农夫带一条狼,一只羊和一筐青菜从河的左岸乘船到右岸,但受到下列条件的限制
有一农夫带一条狼,一只羊和一筐菜从河的左岸乘船到右岸,但受下列条件限制:
(1)船太小,农夫每次只能带一样东西过河
(2)如果没有农夫看管,则狼要吃羊,羊要吃菜
请设计一个过河方案,使得农夫、狼羊都能不受损失的过河。
有一农夫带一条狼,一只羊和一框青菜与从河的左岸乘船倒右岸,但受到下列条件的限制:
(1) 船太小,农夫每次只能带一样东西过河;
(2)如果没有农夫看管,则狼要吃羊,羊要吃菜。
请设计一个过河方案,使得农夫、浪、羊都能不受损失的过河。
题示:
(2) 把每次过河的一种安排作为一种操作,每次过河都必须有农夫,因为只有他可以划船。左岸右岸
解:第一步,定义问题的描述形式
用四元组S=(f,w,s,v)表示问题状态,其中,f,w,s和v分别表示农夫,狼,羊和青菜是否在左岸,它们都可以取1或0,取1表示在左岸,取0表示在右岸。
第二步,用所定义的问题状态表示方式,把所有可能的问题状态表示出来,包括问题的初始状态和目标状态。
由于状态变量有4个,每个状态变量都有2种取值,因此有以下16种可能的状态:
S=(0,0,0,0),S1=(0,0,0,1),S2=(0,0,1,0),S3=(0,0,1,1)
S4=(0,1,0,0),S5=(0,1,0,1),S6=(0,1,1,0),S7=(0,1,1,1)
S8=(1,0,0,0),S9=(1,0,0,1),S10=(1,0,1,0),S11=(1,0,1,1)
S12=(1,1,0,0),S13=(1,1,0,1),S14=(1,1,1,0),S15=(1,1,1,1)
其中,状态S3,S6,S7,S8,S9,S12是不合法状态,S和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)
第四步,根据上述定义的状态和操作进行求解。
发布评论