渡河問題

渡河問題（英語：River crossing puzzle）是著名的益智遊戲，是在一些規則下求最短路徑的解。網路上有許多以動態遊戲的方式呈現這些渡河問題，常使用圖論(graph theory)來表示與解決渡河問題。以圖(graph)表式解決渡河問題的過程，以節點(node)表示狀態，以邊(edge)表示流程。

網路上最常見的渡河問題

人、狼、羊、白菜渡河問題：(狐狸、鵝、豆子問題) 人、狼、羊、白菜要從河的此岸藉由一艘船渡河至另一岸，其中只有人會劃船，每次人只能帶一件東西搭船渡河， 且狼和羊、羊和白菜不能在無人監視的情況下放在一起。 在這些條件下，在最小渡河次數下如何才能讓大家都渡河至另一河岸?

ANS:

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

進階的渡河問題

• 傳教士和吃人惡魔問題

參考資料

• 渡河問題遊戲