过河问题

过河问题（英语：River crossing puzzle）是著名的益智游戏，是在一些规则下求最短路径的解。网络上有许多以动态游戏的方式呈现这些渡河问题，常使用图论(graph theory)来表示与解决渡河问题。以图(graph)表式解决渡河问题的过程，以节点(node)表示状态，以边(edge)表示流程。

网路上最常见的渡河问题

人、狼、羊、白菜渡河问题：(狐狸、鹅、豆子问题) 人、狼、羊、白菜要从河的此岸借由一艘船渡河至另一岸，其中只有人会划船，每次人只能带一件东西搭船渡河， 且狼和羊、羊和白菜不能在无人监视的情况下放在一起。 在这些条件下，在最小渡河次数下如何才能让大家都渡河至另一河岸?

ANS:

 (1)人带羊过河
 (2)人回来
 (3)人带狼(或白菜)过河
 (4)人带羊回来
 (5)人带白菜(或狼)过河
 (6)人回来
 (7)人带羊过河

参考资料

• 渡河问题游戏