图论作业人狼羊菜

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