欢迎来到天天文库
浏览记录
ID：57275107
大小：212.00 KB
页数：2页
时间：2020-08-08
《图论作业人狼羊菜.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二题：某人带着狼、羊以及蔬菜渡河,一小船除需人划外,每次只能载一物过河.而人不在场时,狼要吃羊,羊要吃菜,问此人应该如何渡河.请用最短路求解.解：问题分析：人，狼，羊和菜之间的组合个数有但是由于羊和狼不能共存，羊和菜不能共存，所以可行的组合数为（人狼羊菜），（人狼羊），（人狼菜），（人羊菜），（人羊），（狼菜），（狼），（菜），（羊），（空）共10种状态。我们建立以下的一个图，每条路标示这十种状态之间的相互转换。图中所有的路表示可行的转移路线。问题求解:问题的求解就变成了求解从（人狼羊菜）到（空）的最短路运用Dijkstra算法容易求得最短路（人狼羊菜）→（狼菜）
2、→（人狼菜）→（菜）→（人羊菜）→（羊）→（人羊）→（空）或是（人狼羊菜）→（狼菜）→（人狼菜）→（狼）→（人狼羊）→（羊）→（人羊）→（空）
此文档下载收益归作者所有
