4.5有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1)船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。
解：
首先，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。
其次，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。可能的状态有： 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分别是初始状态和目标状态。
再次，由于每次过河船上都必须有农夫，且除农夫外船上只能其中一种，定义如下：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)
最后:状态空间图如下
3.8解：最短路径为ACDEBA=30
原文：http://www.cnblogs.com/groug/p/4358287.html