3.5 有一农夫带一条狼，一只羊和一筐菜欲从河的左岸乘船到右岸，但受到下列条件的限制：
（1）船太小，农夫每次只能带一样东西过河；
（2）如果没有农夫看管，则狼要吃羊，羊要吃菜。
请设计一个过河方案，使得农夫，狼，羊都能不受损失地过河，画出相应的状态空间图。
提示：（1）用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。
（2）把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。
解：A，B，C，D各代表农夫，狼，羊，菜，用四元组（A，B，C，D）表示状态，A（0）表示在左岸，A（1）表示在右岸。对应的，其它三个元素也是如此。
问题的原始状态；
A（0） B（0） C（0） D（0）
问题的目标状态：
A（1） B（1） C（1） D（1）
方案一：
（1） 农夫先带羊过河，然后农夫回来，羊留在右岸；
（2） 农夫带狼过河，然后农夫带着羊回来，狼留在右岸；
（3） 农夫再带菜过河，然后农夫回来，菜留在右岸；
（4） 农夫带着羊一起过河，完成过河。
状态图：
(A(0) B(0) C(0) D(0))——>(A(1) B(0) C(1) D(0))——>(A(0) B(0) C(1) D(0))——>(A(1) B(1) C(1) D(0))——>(A(0) B(1) C(0) D(0))——>(A(1) B(1) C(0) D(1))——>(A(0) B(1) C(0) D(1))——>(A(1) B(1) C(1) D(1))
方案二：
（1） 农夫先带羊过河，然后农夫回来，羊留在右岸；
（2） 农夫带菜过河，然后农夫带着羊回来，菜留在右岸；
（3） 农夫再带狼过河，然后农夫回来，狼留在右岸；
（4） 农夫带着羊一起过河，完成过河。
(A(0) B(0) C(0) D(0))——>(A(1) B(0) C(1) D(0))——>(A(0) B(0) C(1) D(0))——>(A(1) B(0) C(1) D(1))——>(A(0) B(0) C(0) D(1))——>(A(1) B(1) C(0) D(1))——>(A(0) B(1) C(0) D(1))——>(A(1) B(1) C(1) D(1))
3.8 图3.28是五个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其他各城一次且仅一次，最后回到A城，请找出一条最优路线。
解：所有路径有：
(1)A-B-C-D-E-A，费用=10+8+3+9+11=41. (13)A-B-C-E-D-A，费用=10+8+8+9+9=44.
(2)A-B-D-C-E-A，费用=10+12+3+8+11=44. (14)A-B-D-E-C-A，费用=10+12+9+8+2=41.
(3)A-B-E-C-D-A，费用=10+6+8+3+9=36. (15)A-B-E-D-C-A，费用=10+6+9+3+2=30.
(4)A-C-B-D-E-A，费用=2+8+12+9+11=42. (16)A-C-B-E-D-A，费用=2+8+6+9+9=34.
(5)A-C-D-B-E-A，费用=2+3+12+6+11=34. (17)A-C-D-E-B-A，费用=2+3+9+6+10=30.
(6)A-C-E-B-D-A，费用=2+8+6+12+9=37. (18)A-C-E-D-B-A，费用=2+8+9+12+10=41.
(7)A-D-B-C-E-A，费用=9+12+8+8+11=48. (19)A-D-B-E-C-A，费用=9+12+6+8+2=37.
(8)A-D-C-B-E-A，费用=9+3+8+6+11=37. (20)A-D-C-E-B-A，费用=9+3+8+6+10=36.
(9)A-D-E-C-B-A，费用=9+9+8+8+10=44. (21)A-D-E-B-C-A，费用=9+9+6+8+2=34.
(10)A-E-B-C-D-A，费用=11+6+8+3+9=37. (22)A-E-B-D-C-A，费用=11+6+12+3+2=34.
(11)A-E-C-B-D-A，费用=11+8+8+12+9=48. (23)A-E-C-D-B-A，费用=11+8+3+12+10=44.
(12)A-E-D-B-C-A，费用=11+9+12+8+2=42. (24)A-E-D-C-B-A，费用=11+9+3+8+10=41.
可以看出，花费最短的是(15)A-B-E-D-C-A，(17)A-C-D-E-B-A，它们费用相同=30.
原文：http://www.cnblogs.com/mmy12/p/4357769.html