3.5
解：
初始状态：农夫、狼、羊、菜在河的左岸。
后继函数：农夫和狼过河、农夫和羊过河、农夫和菜过河、农夫一个人过河
测试目标：农夫、狼、羊、菜都安全到达河右岸。
路径耗散：每步耗散值为1，整个过程的耗散值为过河的次数。
解决办法：农夫先载着羊过河，将羊放到对岸之后一人返回，再载着狼过河，将狼放到对岸之后载上羊一同返回河岸，再将羊放置在起始点，将菜载过河之后一人返回最后将羊载到河对岸。
设四元组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表示已过河；
其中（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城
后继函数：分别到B城，C城，D城，E城。
测试目标：且仅一次经过其他城市回到A城，同时费用最少。
路径耗散：城市之间的路程距离和经过路程所花的费用。
五个城市可以组成以下路径：
(1)A-B-C-D-E-A， 代价=10+8+3+9+11=41. (2)A-B-C-E-D-A， 代价=10+8+8+9+9=44.
(3)A-B-D-C-E-A， 代价=10+12+3+8+11=44.(4)A-B-D-E-C-A， 代价=10+12+9+8+2=41.
(5)A-B-E-C-D-A， 代价=10+6+8+3+9=36. (6)A-B-E-D-C-A， 代价=10+6+9+3+2=30.
(7)A-C-B-D-E-A， 代价=2+8+12+9+11=42. (8)A-C-B-E-D-A， 代价=2+8+6+9+9=34.
(9)A-C-D-B-E-A， 代价=2+3+12+6+11=34. (10)A-C-D-E-B-A，代价=2+3+9+6+10=30.
(11)A-C-E-B-D-A，代价=2+8+6+12+9=37. (12)A-C-E-D-B-A，代价=2+8+9+12+10=41.
(13)A-D-B-C-E-A，代价=9+12+8+8+11=48. (14)A-D-B-E-C-A，代价=9+12+6+8+2=37.
(15)A-D-C-B-E-A，代价=9+3+8+6+11=37. (16)A-D-C-E-B-A，代价=9+3+8+6+10=36.
(17)A-D-E-C-B-A，代价=9+9+8+8+10=44. (18)A-D-E-B-C-A，代价=9+9+6+8+2=34.
(19)A-E-B-C-D-A，代价=11+6+8+3+9=37. (20)A-E-B-D-C-A，代价=11+6+12+3+2=34.
(21)A-E-C-B-D-A，代价=11+8+8+12+9=48. (22)A-E-C-D-B-A，代价=11+8+3+12+10=44.
(23)A-E-D-B-C-A，代价=11+9+12+8+2=42.
可以看出，最优路线为 A-B-E-C-D-A
最优路程为A—C—D—E—B—A
路程为：10+6+9+3+2=30
第一次作业
原文：http://www.cnblogs.com/define123456/p/4358053.html
