第一次作业《人工智能》

3.5 有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：

1）船太小，农夫每次只能带一样东西过河。

2）如果没农夫看管，则狼要吃羊，羊要吃菜。

  请设计一个过桥方案，使得农夫、狼、羊、菜都不受损失地过河。画出相应状态空间图。

提示：（1）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。

（2）把每次过河的一次安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。

解：设A=（A1，A2，A3，A4）为状态 

A1：表示农夫的位置，=0：未过河、=1：已过河

A2：表示狼的位置，=0：未过河、=1：已过河

A3：表示菜的位置，=0：未过河、=1：已过河  

A4：表示羊的位置，=0：未过河、=1：已过河

具体的过河方案为：

（1）农夫、羊从左岸-》右岸，留下羊-》一人回到左岸

（2）农夫、菜从左岸-》右岸，留下菜-》农夫、羊回到左岸

（3）农夫、狼从左岸-》右岸，留下菜、狼-》农夫一人回到左岸

（4）农夫、羊从左岸-》右岸

 相应的状态空间图为：（0，0，0，0） (1，0，0，1）

　　 （0，0，0，1） （1，0，1，1） （0，0，1，0）

 　　（1，1，1，0） （0，1，1，0） （1，1，1，1）

 其中（0，0，0，0）为初始状态，（1，1，1，1）为终止状态。