《摆渡过河分析(共2页).doc》由会员分享，可在线阅读，更多相关《摆渡过河分析(共2页).doc（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上摆渡过河问题重述:一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去，但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去？问题分析：由题意知人划船一次只能运三者之一或者自己独自划船，且无论在河的左岸还是右岸都要保证无人情况下狼和山羊，山羊和卷心菜不能单独在一起。在这里，羊所受的限制条件是最多的，所以羊只能独处或在船上被带走，因此, A：人首先只能把山羊带去河的对岸（右岸），将山羊放在右岸； B：人自己回来，可以带狼过去也可以带卷心菜过去，若带卷心菜去对岸， 因为卷
2、心菜不能与山羊在一起，所以人回来时要将山羊再带回左岸； C：人将山羊留在左岸，带狼去对岸，将狼放在右岸； D：人自己回来再将山羊带去对岸。用图论方法：对于人，狼，山羊，卷心菜的位置状态，可用1表示在左岸，用0表示不在左岸，则由无人情况下狼和山羊，山羊和卷心菜不能单独在一起，列出可以存在的状态如下表：状态点名字人狼山羊卷心菜A1111B0101C1101D0100E1110F0010G1010H1011I0001J0000注释：A表示人，狼，山羊，卷心菜都在河的左岸；B表示狼和卷心菜在河的左岸，人和山羊在河的对岸（右岸）将上表中各种状态作为顶点，将两个可以转变的状态点之间连一条有向边，可得到下图摆渡人把他们运过河去，最优方案是从上面有向图中找到一条从A点到J 点的最短路径。即ABCIHFGJ或者ABCDEFGJ.专心-专注-专业