首页 > 其他 > 详细

第一次作业

时间:2015-03-22 23:53:10      阅读:208      评论:0      收藏:0      [点我收藏+]

 

习题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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!