图论作业人狼羊菜(共2页).doc

会员专享推荐 · 你可能也用得上更多

开通会员，畅读全站文档

本篇文档已为你保留

本篇文档价值 ~~¥35.00~~会员免费解锁

全文不限次阅读，剩余内容即刻解锁
高速下载通道，免排队、无等待
专属客服 1 对 1 答疑，优先响应
每日赠送下载券，本篇文档免费送

有 86 篇商业计划书正在上传

下载原文档

第二题：某人带着狼、羊以及蔬菜渡河,一小船除需人划外,每次只能载一物过河.而人不在场时,狼要吃羊,羊要吃菜,问此人应该如何渡河.请用最短路求解.解：问题分析：人，狼，羊和菜之间的组合个数有但是由于羊和狼不能共存，羊和菜不能共存，所以可行的组合数为（人狼羊菜），（人狼羊），（人狼菜），（人羊菜），（人羊），（狼菜），（狼），（菜），（羊），（空）共10种状态。我们建立以下的一个图，每条路标示这十种状态之间的相互转换。图中所有的路表示可行的转移路线。问题求解:问题的求解就变成了求解从（人狼羊菜）到（空）的最短路运用Dijkstra算法容易求得最短路（人狼羊菜）→（狼菜）→（人狼菜）→（菜）→（人羊菜）→（羊）→（人羊）→（空）或是（人狼羊菜）→（狼菜）→（人狼菜）→（狼）→（人狼羊）→（羊）→（人羊）→（空）。