习题3.5
有一农夫带一条狼，一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：
（1）船太小，农夫每次只能带一样东西过河；
（2）如果没有农夫看管，则狼要吃羊，羊要吃菜。
过河方案：
（1）农夫划船把羊从左岸到右岸，留下羊，农夫单独返回左岸；
（2）农夫划船把狼从左岸到右岸，留下狼，农夫再划船把羊送回左岸；
（3）农夫划船把菜从左岸到右岸，留下菜，农夫再单独返回左岸；
（4）农夫最后把羊从左岸到右岸。
相应的状态：（0,0,0,0）->（1,0,1,0）->（0,0,1,0）->（1,1,1,0）->（0,1,0,0）->（1,0,0，1）->（0,1,0,1）->（1,1,1,1）
习题3.8
如图是五个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其他各城一次仅且一次，最后回到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. (24)A-E-D-C-B-A，代价=11+9+3+8+10=41.
不难可以看出最短路径是 (6)A-B-E-D-C-A 和(10)A-C-D-E-B-A，他们是同一条路径。
原文：http://www.cnblogs.com/wangyutang/p/4358167.html