算法系列之十四：狼、羊、菜和农夫过河问题

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

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

农夫带羊过河

农夫返回

农夫带狼过河

农夫带羊返回

农夫带菜过河

农夫返回

农夫带羊过河

<结束>

再看一个答案：

农夫带羊过河

农夫返回

农夫带菜过河

农夫带羊返回

农夫带狼过河

农夫返回

农夫带羊过河

<结束>

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

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

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

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

农夫单独过河；

农夫带狼过河；

农夫带羊过河；

农夫带菜过河；

农夫单独返回；

农夫带狼返回；

农夫带羊返回；

农夫带菜返回；

本题的广度搜索边界就是这8个动作，依次对这8个动作进行遍历最多可以转换为8个新状态，每个新状态又最多可以转化为8个新新状态，就形成了每个状态节点有8个（最多8个）子节点的状态树（八叉树）。本题算法的核心就是对这个状态树进行深度优先遍历，当某个状态满足结束状态时就输出一组结果。

需要注意的是，并不是每个动作都可以得到一个新状态，比如“农夫带狼过河”这个动作，对于那些狼已经在河对岸的状态就是无效的，无法得到新状态，因此这个八叉树并不是满树。除此之外，题目要求的合法性判断也可以砍掉很多无效的状态。最后一点需要注意的是，即使是有效的状态，也会有重复，在一次深度遍历的过程中如果出现重复的状态可能会导致无穷死循环，因此要对重复出现的状态进行“剪枝”。

程序实现首先要描述状态模型，本算法的状态定义为：

33struct ItemState

34{

35 ......

43 State farmer,wolf,sheep,vegetable;

44 Action curAction;

35 ......

45};

算法在穷举的过程中需要保存当前搜索路径上的所有合法状态，考虑到是深度优先算法，用Stack是最佳选择，但是Stack没有提供线性遍历的接口，在输出结果和判断是否有重复状态时都需要线性遍历保存的状态路径，所以本算法不用Stack，而是用Deque（双端队列）。

整个算法的核心就是ProcessState()函数，ProcessState()函数通过对自身的递归调用实现对状态树的遍历，代码如下：

291void ProcessState(deque<ItemState>& states)

292{

293 ItemState current = states.back(); /*每次都从当前状态开始*/

294 if(current.IsFinalState())

295 {

296 PrintResult(states);

297 return;

298 }

299

300 ItemState next;

301 for(int i = 0; i < action_count; ++i)

302 {

303 if(actMap[i].processFunc(current, next))

304 {

305 if(IsCurrentStateValid(next) && !IsProcessedState(states, next))

306 {

307 states.push_back(next);

308 ProcessState(states);

309 states.pop_back();

310 }

311 }

312 }

313}

参数states是当前搜索的状态路径上的所有状态列表，所以ProcessState()函数首先判断这个状态列表的最后一个状态是不是最终状态，如果是则说明这个搜索路径可以得到一个解，于是调用PrintResult()函数打印结果，随后的return表示终止设个搜索路径上的搜索。如果还没有达到最终状态，则依次从8个固定的过河动作得到新的状态，并从新的状态继续搜索。为了避免长长的switch…case语句，程序算法使用了表驱动的方法，将8个固定过河动作的处理函数放在一张映射表中，用简单的查表代替switch…case语句。映射表内容如下：

279ActionProcess actMap[action_count] =

280{

281 { FARMER_GO, ProcessFarmerGo },

282 { FARMER_GO_TAKE_WOLF, ProcessFarmerGoTakeWolf },

283 { FARMER_GO_TAKE_SHEEP, ProcessFarmerGoTakeSheep },

284 { FARMER_GO_TAKE_VEGETABLE, ProcessFarmerGoTakeVegetable },

285 { FARMER_BACK, ProcessFarmerBack },

286 { FARMER_BACK_TAKE_WOLF, ProcessFarmerBackTakeWolf },

287 { FARMER_BACK_TAKE_SHEEP, ProcessFarmerBackTakeSheep },

288 { FARMER_BACK_TAKE_VEGETABLE, ProcessFarmerBackTakeVegetable }

289};

表中的处理函数非常简单，就是根据当前状态以及过河动作，得到一个新状态，如果过河动作与当前状态矛盾，则返回失败，以FARMER_GO_TAKE_WOLF动作对应的处理函数ProcessFarmerGoTakeWolf()为例，看看ProcessFarmerGoTakeWolf()函数的代码：

182bool ProcessFarmerGoTakeWolf(const ItemState& current, ItemState& next)

183{

184 if((current.farmer != HERE) || (current.wolf != HERE))

185 return false;

186

187 next = current;

188

189 next.farmer = THERE;

190 next.wolf = THERE;

191 next.curAction = FARMER_GO_TAKE_WOLF;

192

193 return true;

194}

当过河动作对应的处理函数返回成功，表示可以得到一个不矛盾的新状态时，就要对新状态进行合法性检查，首先是检查是否满足题目要求，比如狼和羊不能独处以及羊和菜不能独处，等等，这个检查在IsCurrentStateValid()函数中完成。接着是检查新状态是否和状态路径上已经处理过的状态有重复，这个检查由IsProcessedState()函数完成，IsProcessedState()函数的实现也很简单，就是遍历states，与新状态比较是否有相同状态，代码如下：

131bool IsProcessedState(deque<ItemState>& states, ItemState& newState)

132{

133 deque<ItemState>::iterator it = find_if( states.begin(), states.end(),

134 bind2nd(ptr_fun(IsSameItemState), newState) );

135

136 return (it != states.end());

137}

运行程序，最终得到的结果是：

Find Result 1:

Unknown action, item states is : 0 0 0 0

Farmer take sheep go over river, item states is : 1 0 1 0

Farmer go back, item states is : 0 0 1 0

Farmer take wolf go over river, item states is : 1 1 1 0

Farmer take sheep go back, item states is : 0 1 0 0

Farmer take vegetable go over river, item states is : 1 1 0 1

Farmer go back, item states is : 0 1 0 1

Farmer take sheep go over river, item states is : 1 1 1 1

Find Result 2:

Unknown action, item states is : 0 0 0 0

Farmer take sheep go over river, item states is : 1 0 1 0

Farmer go back, item states is : 0 0 1 0

Farmer take vegetable go over river, item states is : 1 0 1 1

Farmer take sheep go back, item states is : 0 0 0 1

Farmer take wolf go over river, item states is : 1 1 0 1

Farmer go back, item states is : 0 1 0 1

Farmer take sheep go over river, item states is : 1 1 1 1

看来确实是只有两种结果。