狼羊菜过河：船小只能带一个

题目

农夫带着狼、羊、菜来到河边，只有一条小船，每次除农夫外只能带一样过河。若农夫不在场：

• 狼会吃羊；
• 羊会吃菜。

怎样把它们都安全运过去？

答案与解析

关键：绝不能把“狼+羊”或“羊+菜”单独留在一边。最少 7 次渡河（去4回3）：

1. 带羊过河（左岸剩狼、菜，安全）， Farmer+羊 → 右
2. 农夫空手返回
3. 带狼（或菜）过河，此时右岸有狼、羊——不行！所以带狼过去后，把羊带回来
4. 把羊带回左岸，带菜过河（右岸狼、菜安全）， Farmer+菜 → 右
5. 农夫空手返回
6. 带羊过河

完成。若第 3 步先带菜，对称地同样 7 步解决。

背后的数学

这是流传千年的过河谜题（river crossing），是状态空间搜索的启蒙：把“两岸各有什么”当作状态，合法移动为边，找一条从初态到目标态的路径。后来发展为图搜索（BFS/DFS）与约束满足问题（CSP）的经典教学案例。现代自动驾驶的“路径+约束”规划，思维骨架与此同源。