习题3.5
答:方案:农夫先带羊到右岸,羊留在右岸;
然后回左岸带狼到右岸,狼留在右岸;
把在右岸的羊带回左岸,接着把菜带到右岸,最后回到左岸将羊带到右岸。
用四元组(农夫,狼,羊,菜)表示状态,其中每个元素都为0或1,用0表示在左岸,用1表示在右岸。则整个方案状态如下:
(0,0,0,0)、(1,0,1,0)、(0,0,1,0)、(1,1,1,0)、(0,1,0,0)、(1,1,0,1)、(0,1,0,1)、(1,1,1,1)
状态空间图:
习题3.8
如图,从A城出发,经过其他各城一次且仅一次,最后回到A城的所有路线和费用有:
1.ABECDA,费用=10+6+8+3+9=36
2.ABCDEA,费用=10+8+3+9+11=41 14.ABCEDA,费用=10+8+8+9+9=44.
3.ABDCEA,费用=10+12+3+8+11=44 15.ABDECA,费用=10+12+9+8+2=41.
4.ACBDEA,费用=2+8+12+9+11=42. 16.ACBEDA,费用=2+8+6+9+9=34.
5.ACDBEA,费用=2+3+12+6+11=34. 17.ACDEBA,费用=2+3+9+6+10=30.
6.ACEBDA,费用=2+8+6+12+9=37. 18.ACEDBA,费用=2+8+9+12+10=41.
7.ADBCEA,费用=9+12+8+8+11=48. 19.ADBECA,费用=9+12+6+8+2=37.
8.ADCBEA,费用=9+3+8+6+11=37. 20.ADCEBA,费用=9+3+8+6+10=36.
9.ADECBA,费用=9+9+8+8+10=44. 21.ADEBCA,费用=9+9+6+8+2=34.
10.AEBCDA,费用=11+6+8+3+9=37. 22.AEBDCA,费用=11+6+12+3+2=34.
11.AECBDA,费用=11+8+8+12+9=48. 23.AECDBA,费用=11+8+3+12+10=44.
12.AEDBCA,费用=11+9+12+8+2=42. 24.AEDCBA,费用=11+9+3+8+10=41.
13.ABEDCA,费用=10+6+9+3+2=30.
可以看出,费用最短的是13.ABEDCA,17.ACDEBA,它们费用相同=30,即为它们为最优线路。
原文:http://www.cnblogs.com/luoyun221/p/4358129.html