首页 / 软件开发 / 数据结构与算法 / 算法系列（十四） 狼、羊、菜和农夫过河问题

算法系列（十四） 狼、羊、菜和农夫过河问题2014-04-30 csdn博客 吹泡泡的小猫题目描述：农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农 夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。 请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。

这个题目考察人的快速逻辑运算和短期记忆力。分析一下，在狼－》羊－》菜这个食物链条中 ，“羊”处在关键位置，解决问题的指导思想就是将“羊”与“狼”和“菜”始终处于隔离状态，也 就是说“羊”应该总是最后被带过河的。来看一个答案：

农夫带羊过河

农夫返回

农夫带狼过河

农夫带羊返回

农夫带菜过河

农夫返回

农夫带羊过 河

<结束>

再看一个答案：

农夫带羊过河

农夫返回

农夫带 菜过河

农夫带羊返回

农夫带狼过河

农夫返回

农夫带羊过河

< 结束>

解决问题都是围绕着羊进行的。

上面已经提到了两个答案，那么，这个问题 到底有多少中答案呢？答案还需要用计算机进行穷举。用计算机解决这个问题的关键还是状态遍历， 这个和《算法系列――三个水桶均分水问题》一文中提到的状态遍历是一个道理，归根到底就是一个 有限状态机。农夫、狼、羊和菜根据它们的位置关系可以有很多个状态，但总的状态数还是有限的， 我们的算法就是在这些有限个状态之间遍历，直到找到一条从初始状态转换到终止状态的“路径”， 并且根据题目的要求，这条“路径”上的每一个状态都应该是合法的状态。

本题无论是状态建 模还是状态转换算法，都比“用三个水桶均分8升水”要简单。首先是状态，农夫、狼、羊和菜做为四 个独立的Item，它们的状态都很简单，要么是过河，要么是没有过河，任意时刻每个Item的状态只有 一种。如果用“HERE”表示没有过河，用“THERE”表示已经过河，用[农夫，狼，羊，菜]四元组表示 某个时刻的状态，则本题的状态空间就是以[HERE，HERE，HERE，HERE]为根的一棵状态树，当这个状 态树的某个叶子节点是状态[THERE，THERE，THERE，THERE]，则表示从根到这个叶子节点之间的状态 序列就是本问题的一个解。

本题的状态转换算法依然是对状态空间中所有状态进行深度优先搜 索，因为狼、羊和菜不会划船，所以状态转换算法也很简单，不需要象“用三个水桶均分8升水”问题 那样要用排列组合的方式确定转换方法（倒水动作），本题一共只有8种固定的状态转换运算（过河动 作），分别是：

农夫单独过河；

农夫带狼过河；

农夫带羊过河；

农夫 带菜过河；

农夫单独返回；

农夫带狼返回；

农夫带羊返回；

农夫带菜 返回；