渡河問題
外观
此條目需要补充更多来源。 (2010年5月23日) |
过河问题(英語:River crossing puzzle)是著名的益智遊戲,是在一些规则下求最短路徑的解。网络上有許多以動態遊戲的方式呈現這些渡河問題,常使用圖論(graph theory)來表示與解決渡河問題。以圖(graph)表式解決渡河問題的過程,以節點(node)表示狀態,以邊(edge)表示流程。
網路上最常見的渡河問題
[编辑]人、狼、羊、白菜渡河問題:(狐狸、鵝、豆子問題) 人、狼、羊、白菜要从河的此岸藉由一艘船渡河至另一岸,其中只有人會划船,每次人只能帶一件東西搭船渡河, 且狼和羊、羊和白菜不能在無人監視的情況下放在一起。 在這些條件下,在最小渡河次數下如何才能讓大家都渡河至另一河岸?
ANS:
(1)人带羊过河 (2)人回来 (3)人带狼(或白菜)过河 (4)人带羊回来 (5)人带白菜(或狼)过河 (6)人回来 (7)人带羊过河