狼、羊、菜和农夫过河
题目描述：
农夫需要把狼、羊、菜和自己运到河对岸去（不知道为啥要运狼，别问我），只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手的问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。
算法设计思路
这是一个很简单的问题，在狼、羊和菜这个食物链上，关键是中间的羊，因为狼不吃菜，所以要安全过河，农夫的第一件事就是带羊走，拆开这个食物链。但是计算机无法理解这个关键的羊，所以我们仍然采用穷举法来解决这个问题，同时借助于穷举搜索找出所有过河的方法。
这个题目的解决思路和“三个水桶倒水”问题的解决思路类似，就是对状态进行穷举搜索，从初始状态开始穷举所有的状态变化，直到某一次变化后得到问题解决的最终状态，就输出一个结果。前面的几课中已经多次提到穷举法的两个关键步骤，这里不再列出。接下来就直接从这两个步骤入手，介绍如何设计这个问题的穷举算法。
定义问题的状态
在确定以何种方法对解空间进行穷举搜索之前，首先要定义问题的解。虽然这个题目的要求是给出农夫带着他的小伙伴过河的动作，但是单纯考虑对动作的穷举是没有意义的，因为问题最后的解决状态是农夫、狼、羊和菜过到河对岸，能最终产生这种状态的动作才有意义，为了判断动作的有效性，需要定义一个合适的状态来描述这个游戏在某个时刻的局面。考虑一下这个题目涉及的所有元素：农夫、狼、羊、菜、船和河，河是固定的，没有状态变化，因为只有农夫可以划船，所以船可以看作和农夫是一体的，简化后其实有 4 个元素需要考虑，分别是农夫、狼、羊和菜。如图（1）所示的一种过河的过程，状态的定义只要能表达农夫、狼、羊和菜的位置关系即可。
从图（1）可以看出来，状态(a)到(h)变化的其实就是这 4 个元素的位置，每个元素的位置只有两个状态，即在河的左岸和在河的右岸；问题的初始状态是农夫、狼、羊和菜都在河的左岸，得到解的终止状态是农夫、狼、羊和菜都在河的右岸。我们用一个四元组来表示四个元素的位置状态，那么初始状态为 [Left，Left，Left，Left]，最终的结果状态为 [Right，Right，Right，Right]。
状态树和解空间
和“三个水桶等分 8 升水”问题一样，对所有状态穷举搜索的结果也是一棵状态树，根节点是初始状态，叶子节点就是解决问题的状态。这个题目由于限制条件比较特殊，只有农夫可以划船，一次只能带一个小伙伴，同时狼、羊和菜又不能愉快的在一起玩耍，所以状态树上很多状态都是非法状态，客观上起到了很好的剪枝效果。如图（2）所示的状态树中，蓝色的状态表示此状态已经和之前的状态重复，红色的状态表示这是一个非法状态，不是出现狼吃羊的情况，就是出现羊吃菜的情况。绿色状态是搜索到了结果状态，这是状态树的叶子节点。
状态树上绿色的节点是要搜索的结果状态，从结果状态到根节点之间的状态序列，就是问题解决的过程，有多个绿色的节点表示有多个解决问题的过程。根据题目的意图，最终的结果是要输出这条转换路径的过河过程，实际上就是与状态转换路径相对应的动作路径，或动作列表。当定义了动作的数学模型后，就可以根据状态图中状态转换路径找到对应的动作列表，依次输出这个路径上每个状态对应的动作就可以得到一个完整的过河过程。
状态的数据模型
根据之前对状态的定义，状态的数据模型就是农夫、狼、羊和菜的位置，位置定义 LOCATION 就是两个状态，LOCATION::LEFT 表示对应的元素在河的左岸，LOCATION::RIGHT 表示对应元素在河的右岸（就是过河状态）。
struct ItemState
{
......
LOCATION farmer,wolf,sheep,vegetable; //四个元素的位置
ACTION curAction; //此状态对应的动作
};curAction 是当前状态绑定的过河动作，即前一个状态通过这个过河动作转变成当前状态。记录状态对应的过河动作的目的是为了能够在输出结果时，按照状态演变序列的顺序输出过河动作。
过河动作的数据模型
两个静态的位置状态是通过过河动作建立关联的，分析这个题目，我们注意到，狼、羊和菜是不会自己过河的，因为只有农夫会划船。农夫可以自己过河，也可以带一个物品过河，当然，从河对岸返回时也是一样的情况。由此可见，本问题的过河动作其实只有 8 个固定动作，分别是：
（1）农夫自己过河 （2）农夫带狼过河 （3）农夫带羊过河 （4）农夫带菜过河 （5）农夫自己返回 （6）农夫带狼返回 （7）农夫带羊返回 （8）农夫带菜返回 把一个状态与以上动作结合，就可以转化得到一个新状态，但是需要注意的是，并不是所有的动作都适用于对应的状态，比如对于农夫在河的左岸的状态，动作（5）~（8）代表的返回动作就都不适用。同样，对于一个菜已经在河对岸的状态，动作（4）就不适用。在搜索过程中对过河动作遍历的时候，要根据这些情况合理的剪掉一些分支。根据以上描述，过河动作 ACTION 定义如下：
num class ACTION
{
GO_SELF,
GO_WITH_WOLF,
GO_WITH_SHEEP,
GO_WITH_VEGETABLE,
BACK_SELF,
BACK_WITH_WOLF,
BACK_WITH_SHEEP,
BACK_WITH_VEGETABLE,
};设计搜索算法
我们讨论的状态都是静止的，如果不是有过河动作作用到状态上，状态是不会发生变化的。对状态树的搜索，其实就是把 8 个过河动作依次与状态结合，演变为新的状态的过程。与“三个水桶等分 8 升水”问题一样，本题的搜索算法依然采用深度优先遍历，从初始状态节点开始，一直搜索到合法状态为止，在这个过程中，需要记录已经搜索过的状态，避免出现重复状态导致算法进入死循环。
状态树的遍历
状态树的遍历就是促使状态树上的一个状态向下一个状态转换的驱动过程，这是一个很重要的部分，如果不能正确地驱动状态变化，就不能实现这个穷举算法，前面提到的动作模型，就是驱动状态变化的关键因子。对于一个状态来说，它能转换到哪些新状态，取决于它能应用哪些过河动作，与此同时，不同的过河动作也会对状态产生不同的变化。比如ACTION::GO_WITH_VEGETABLE动作，将使得 ItemState 中 farmer 和 vegetable 的位置值从 LOCATION::LEFT 转变为 LOCATION::RIGHT。由于 8 个过河动作对状态的影响无法用一个一致的代码逻辑进行处理，所以我们为每个过河动作定义一个代码处理逻辑，8 个动作对应 8 个代码处理逻辑：
struct ActionProcess
{
ACTION act_name;
std::function<bool(const ItemState& current, ItemState& next)> TakeAction;
};
ActionProcess actMap[] =
{
{ ACTION::GO_SELF, ProcessFarmerGo },
{ ACTION::GO_WITH_WOLF, ProcessFarmerGoTakeWolf },
{ ACTION::GO_WITH_SHEEP, ProcessFarmerGoTakeSheep },
{ ACTION::GO_WITH_VEGETABLE, ProcessFarmerGoTakeVegetable },
{ ACTION::BACK_SELF, ProcessFarmerBack },
{ ACTION::BACK_WITH_WOLF, ProcessFarmerBackTakeWolf },
{ ACTION::BACK_WITH_SHEEP, ProcessFarmerBackTakeSheep },
{ ACTION::BACK_WITH_VEGETABLE, ProcessFarmerBackTakeVegetable }
};每个处理逻辑需要做三件事情，首先要判断当前状态是否适用于对应的动作，接着根据对状态进行相应的改变并将对应的动作记录到新状态中，最后判断转化后的状态是不是一个合法的状态。仍然以ACTION::GO_WITH_VEGETABLE动作为例，其处理逻辑 ProcessFarmerGoTakeVegetable() 的实现如下：
bool ProcessFarmerGoTakeVegetable(const ItemState& current, ItemState& next)
{
if((current.farmer != LOCATION::LEFT) || (current.vegetable != LOCATION::LEFT))
return false;
next = current;
next.farmer = LOCATION::RIGHT;
next.vegetable = LOCATION::RIGHT;
next.curAction = ACTION::GO_WITH_VEGETABLE;
return IsCurrentStateValid(next);
}对 8 个动作循环一遍，即可完成对一个状态的遍历，并根据情况生成新的状态，所以，遍历的动作就是对 actMap 做一个循环，依次调用每个动作对应的 TakeAction 逻辑。遍历代码的主体大致是这样的：
ItemState next;
for (auto& act : actMap)
{
if(act.TakeAction(current, next))
{
......
}
}剪枝和优化（重复状态和非法状态判断）
根据图（2）显示的状态树，需要剪枝处理的情况有两种，一种是非法状态，另一种是重复的状态。对非法状态的过滤，体现在过河动作对应的处理逻辑中，ProcessFarmerGoTakeVegetable() 函数中最后调用 IsCurrentStateValid() 判断这个状态是不是合法状态。对于产生非法状态的情况，ProcessFarmerGoTakeVegetable() 函数返回 false，遍历循环就跳过这个动作，继续遍历下一个动作。
对重复状态的过滤，是在 TakeAction 逻辑返回 true 的情况下才进行的，如下代码所示，两个 if 判断就是对上述两种情况的剪枝处理。
if(act.TakeAction(current, next))
{
if(!IsProcessedState(states, next))
{
......
}
}代码实现
搜索算法代码
SearchState() 函数实现状态树的搜索遍历，整体结构和“三个水桶等分 8 升水”问题类似，由两部分内容组成：第一部分中 IsFinalState() 函数判断当前状态序列中最后一个状态是不是最终结果状态，如果是就输出一组状态序列（以及对应的过河动作）；如果当前状态序列中最后一个状态不是结果状态，则转入第二部分开始搜索新的状态。
void SearchStates(deque<ItemState>& states)
{
ItemState current = states.back(); /*每次都从当前状态开始*/
if(current.IsFinalState())
{
PrintResult(states);
return;
}
ItemState next;
for (auto& act : actMap)
{
if(act.TakeAction(current, next))
{
if(!IsProcessedState(states, next))
{
states.push_back(next);
SearchStates(states);
states.pop_back();
}
}
}
}判断非法动作和重复状态
如果农夫不在场，狼会吃羊，羊会吃菜，根据这个描述，无法直接写出代码，把这句话换一种说法，则会更容易转化成代码实现：
如果狼和羊位置相同，并且农夫的位置与它们不同，则是非法状态； 如果羊和菜位置相同，并且农夫的位置与它们不同，则是非法状态； 其他情况均为合法状态。 这样一来，这个判断函数就比较容易用代码描述了：
bool IsCurrentStateValid(const ItemState& current)
{
if ((current.wolf == current.sheep) && (current.sheep != current.farmer))
{
return false;
}
if ((current.vegetable == current.sheep) && (current.sheep != current.farmer))
{
return false;
}
return true;
}重复状态的判断更简单，就是对状态队列进行一次查找操作：
bool IsProcessedState(deque<ItemState>& states, const ItemState& newState)
{
auto it = find_if( states.begin(), states.end(),
[&newState](ItemState& item) { return item.IsSameState(newState); });
return (it != states.end());
}