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

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