习题3（第一次作业）

3.5

　　解：设四元组A=（A1，A2，A3，A4）表示问题初始状态。

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

　　　　　　　　　 A2表示狼的位置：A2=0表示没过河，A2=1表示已过河；

　　　　　　　　　 A3表示羊的位置：A3=0表示没过河，A3=1表示已过河；

　　　　　　　　　 A4表示菜的位置：A4=0表示没过河，A4=1表示已过河；

　　　　具体解决方案：（1）农夫先带羊从左岸到右岸，留下羊再回到左岸；

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

　　　　　　　　　　　（3）农夫带狼从左岸到右岸，留下狼、农夫回到左岸；

　　　　　　　　　　　（4）农夫带羊从左岸到右岸，任务完成；

　　　　其中（A1,A2,A3,A4）=（0 0 0 0）为初始状态，（A1,A2,A3,A4）=（1 1 1 1 ）为终止状态；

　　　　状态空间图：（0 0 0 0）（1 0 1 0） 

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

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

3.8

　　解：初始状态：A　　　　　

　　　　　 目标状态：（AXXXXA）；

　　　　　 路线如下：

　　　　　 最短路线：其最短路经有两条 （1）A-C-D-E-B-A

　　　　　　　　　　　　　　　　　　  （2）A-B-E-D-C-A

　　　　　 路径耗散：（1）A-C-D-E-B-A，耗散=2+3+9+6+10=30；

　　　　　　　　　　 （2）A-B-E-D-C-A，耗散=10+6+9+3+2=30.

习题3（第一次作业）

原文：http://www.cnblogs.com/wdsnn/p/4357879.html