重庆移通学院：《数据结构》课程教学资源（PPT课件讲稿）渡河问题

渡河问题 一个人带了一只狼、一只山羊和一棵白菜想 要渡河。河上有一只独木船,每次除人外只 能带一样东西,另外如果人不在时狼就要吃 山羊,羊就要吃白菜。问应该怎样安排渡河 才能做到既把所有东西都带过河,而且在河 上来回的次数又最少? 设M代表人,W代表狼,S代表山羊,V代表 白菜

渡河问题 一个人带了一只狼、一只山羊和一棵白菜想 要渡河。河上有一只独木船，每次除人外只 能带一样东西，另外如果人不在时狼就要吃 山羊，羊就要吃白菜。问应该怎样安排渡河， 才能做到既把所有东西都带过河，而且在河 上来回的次数又最少？ 设M代表人，W代表狼，S代表山羊，V代表 白菜

渡河问题 算法思想 用集合表示在某岸上的所有情况(16种): MWSW [MWS [MW MSV TWSV [MWI MSI WS [W [SV[M [s] VV 剩下的10种情况按若甲经过一次渡河可变成乙, 那么就在甲与乙之间连一条边由此得到如下图G: MWSV MWS MWV MSV MS MS 空 结论在G中找一条连页点MwV与空,并且包含边数最少的路

渡河问题 算法思想： 用集合表示在某岸上的所有情况（16种）： [MWSV] [MWS] [MWV] [MSV] [WSV] [MW] [MS] [MV] [WS] [WV] [SV] [M] [S] [V] [空] 剩下的10种情况,按若甲经过一次渡河可变成乙, 那么就在甲与乙之间连一条边,由此得到如下图G: MWSV MWS MWV MSV MS MS W S V 空 结论:在G中找一条连接顶点MWSV与空,并且包含边数最少的路