takeaction

狼、⽺、菜和农夫过河问题[超详细解析，CPP实现]

农夫需要把狼、⽺、菜和⾃⼰运到河对岸去（不知道为啥要运狼，别问我），只有农夫能够划船，⽽且船⽐较⼩，除农夫之外每次只

能运⼀种东西，还有⼀个棘⼿的问题，就是如果没有农夫看着，⽺会偷吃菜，狼会吃⽺。请考虑⼀种⽅法，让农夫能够安全地安排这

些东西和他⾃⼰过河。

算法设计思路

这是⼀个很简单的问题，在狼、⽺和菜这个⾷物链上，关键是中间的⽺，因为狼不吃菜，所以要安全过河，农夫的第⼀件事就是带⽺⾛，拆

开这个⾷物链。但是计算机⽆法理解这个关键的⽺，所以我们采⽤穷举法来解决这个问题，同时借助于穷举搜索找出所有过河的⽅法。

定义问题的状态

在确定以何种⽅法对解空间进⾏穷举搜索之前，⾸先要定义问题的解。虽然这个题⽬的要求是给出农夫带着他的⼩伙伴过河的动作，**但是

单纯考虑对动作的穷举是没有意义的，因为问题最后的解决状态是农夫、狼、⽺和菜过到河对岸，能最终产⽣这种状态的动作才有意义，为

了判断动作的有效性，需要定义⼀个合适的状态来描述这个游戏在某个时刻的局⾯。**考虑⼀下这个题⽬涉及的所有元素：农夫、狼、⽺、

菜、船和河，河是固定的，没有状态变化，因为只有农夫可以划船，所以船可以看作和农夫是⼀体的，简化后其实有4个元素需要考虑，

分别是农夫、狼、⽺和菜。如下图所⽰的⼀种过河的过程，状态的定义只要能表达农夫、狼、⽺和菜的位置关系即可。

从上图可以看出来，状态(a)到(h)变化的其实就是这4个元素的位置，每个元素的位置只有两个状态，即在河的左岸和在河的右岸；问题

的初始状态是农夫、狼、⽺和菜都在河的左岸，得到解的终⽌状态是农夫、狼、⽺和菜都在河的右岸。我们⽤⼀个四元组来表⽰四个元素的

位置状态，那么初始状态为[Left,Left,Left,Left]，最终的结果状态为[Right,Right,Right,Right]。

状态树和解空间

对所有状态穷举搜索的结果也是⼀棵状态树，根节点是初始状态，叶⼦节点就是解决问题的状态。**这个题⽬由于限制条件⽐较特殊，只有

农夫可以划船，⼀次只能带⼀个⼩伙伴，同时狼、⽺和菜⼜不能愉快地在⼀起玩耍，所以状态树上很多状态都是⾮法状态，客观上起到了很

好的剪枝效果。**如下图所⽰的状态树中，蓝⾊的状态表⽰此状态已经和之前的状态重复，红⾊的状态表⽰这是⼀个⾮法状态，不是出现狼

吃⽺的情况，就是出现⽺吃菜的情况。绿⾊状态是搜索到了结果状态，这是状态树的叶⼦节点

根据题⽬的意图，最终的结果是要输出这条转换路径的过河过程，实际上就是与状态转换路径相对应的动作路径，或动作列表。当定义了动

作的数学模型后，就可以根据状态图中状态转换路径找到对应的动作列表，依次输出这个路径上每个状态对应的动作就可以得到⼀个完整的

过河过程。

状态的数据模型

根据之前对状态的定义，状态的数据模型就是农夫、狼、⽺和菜的位置，位置定义LOCATION就是两个状态，LOCATION::LEFT表⽰对应

的元素在河的左岸，LOCATION::RIGHT表⽰对应元素在河的右岸（就是过河状态）。

structItemState

{

......

LOCATIONfarmer,wolf,sheep,vegetable;//四个元素的位置

ACTIONcurAction;//此状态对应的动作

};

过河动作的数据模型

两个静态的位置状态是通过过河动作建⽴关联的，因为只有农夫会划船。农夫可以⾃⼰过河，也可以带⼀个物品过河，当然，从河对岸返回

时也是⼀样的情况。由此可见，本问题的过河动作其实只有8个固定动作，分别是：

(1)农夫⾃⼰过河

(2)农夫带狼过河

(3)农夫带⽺过河

(4)农夫带菜过河

(5)农夫⾃⼰返回

(6)农夫带狼返回

(7)农夫带⽺返回

(8)农夫带菜返回

但是需要注意的是，并不是所有的动作都适⽤于对应的状态，⽐如对于农夫在河的左岸的状态，动作（5）~（8）代表的返回动作就都不适

⽤。同样，对于⼀个菜已经在河对岸的状态，动作（4）就不适⽤。在搜索过程中对过河动作遍历的时候，要根据这些情况合理地剪掉⼀些

分⽀。根据以上描述，过河动作ACTION定义如下：

enumclassACTION

{

GO_SELF,

GO_WITH_WOLF,

GO_WITH_SHEEP,

GO_WITH_VEGETABLE,

BACK_SELF,

BACK_WITH_WOLF,

BACK_WITH_SHEEP,

BACK_WITH_VEGETABLE,

};

设计搜索算法

我们讨论的状态都是静⽌的，如果不是有过河动作作⽤到状态上，状态是不会发⽣变化的。对状态树的搜索，其实就是把8个过河动作依

次与状态结合，演变为新的状态的过程。本题的搜索算法采⽤深度优先遍历，从初始状态节点开始，⼀直搜索到合法状态为⽌，在这个过程

中，需要记录已经搜索过的状态，避免出现重复状态导致算法进⼊死循环。

状态树的遍历

不同的过河动作也会对状态产⽣不同的变化。⽐如ACTION::GO_WITH_VEGETABLE动作，将使得ItemState中farmer和vegetable的位置

值从LOCATION::LEFT转变为LOCATION::RIGHT。由于8个过河动作对状态的影响⽆法⽤⼀个⼀致的代码逻辑进⾏处理，所以我们为每个

过河动作定义⼀个代码处理逻辑，8个动作对应8个代码处理逻辑：

structActionProcess

{

ACTIONact_name;

std::functionTakeAction;

};

ActionProcessactMap[]=

{

{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()的实现如下：

boolProcessFarmerGoTakeVegetable(constItemState¤t,ItemState&next)

{

if((!=LOCATION::LEFT)||(ble!=LOCATION::LEFT))

returnfal;

next=current;

=LOCATION::RIGHT;

ble=LOCATION::RIGHT;

ion=ACTION::GO_WITH_VEGETABLE;

returnIsCurrentStateValid(next);

}

对8个动作循环⼀遍，即可完成对⼀个状态的遍历，并根据情况⽣成新的状态，所以，遍历的动作就是对actMap做⼀个循环，依次调⽤

每个动作对应的TakeAction逻辑。遍历代码的主体⼤致是这样的：

ItemStatenext;

for(auto&act:actMap)

{

if(tion(current,next))

{

......

}

}

需要剪枝处理的情况有两种，⼀种是⾮法状态，另⼀种是重复的状态。对⾮法状态的过滤，体现在过河动作对应的处理逻辑

中，ProcessFarmerGoTakeVegetable()函数中最后调⽤IsCurrentStateValid()判断这个状态是不是合法状态。对于产⽣⾮法状态的情

况，ProcessFarmerGoTakeVegetable()函数返回fal，遍历循环就跳过这个动作，继续遍历下⼀个动作。

对重复状态的过滤，是在TakeAction逻辑返回true的情况下才进⾏的，如下代码所⽰，两个if判断就是对上述两种情况的剪枝处理。

if(tion(current,next))

{

if(!IsProcesdState(states,next))

{

......

}

}

代码实现

搜索算法代码

SearchState()函数实现状态树的搜索遍历，由两部分内容组成：第⼀部分的IsFinalState()函数判断当前状态序列中最后⼀个状态是不是最

终结果状态，如果是就输出⼀组状态序列（以及对应的过河动作）；如果当前状态序列中最后⼀个状态不是结果状态，则转⼊第⼆部分开始

搜索新的状态。

voidSearchStates(deque&states)

{

ItemStatecurrent=();/*每次都从当前状态开始*/

if(lState())

{

PrintResult(states);

return;

}

ItemStatenext;

for(auto&act:actMap)

{

if(tion(current,next))

{

if(!IsProcesdState(states,next))

{

_back(next);

SearchStates(states);

_back();

}

}

}

}

判断⾮法动作和重复状态

如果狼和⽺位置相同，并且农夫的位置与它们不同，则是⾮法状态；

如果⽺和菜位置相同，并且农夫的位置与它们不同，则是⾮法状态；

其他情况均为合法状态。

boolIsCurrentStateValid(constItemState¤t)

{

if((==)&&(!=))

{

returnfal;

}

if((ble==)&&(!=))

{

returnfal;

}

returntrue;

}

重复状态的判断更简单，就是对状态队列进⾏⼀次查找操作：

boolIsProcesdState(deque&states,constItemState&newState)

{

autoit=find_if((),(),

[&newState](ItemState&item){State(newState);});

return(it!=());

}

完整代码

#include

#include

#include

#include

#include

#include

#include

#include

enumclassLOCATION

{

LEFT,

RIGHT

};

enumclassACTION

{

GO_SELF,

GO_WITH_WOLF,

GO_WITH_SHEEP,

GO_WITH_VEGETABLE,

BACK_SELF,

BACK_WITH_WOLF,

BACK_WITH_SHEEP,

BACK_WITH_VEGETABLE,

INVALID,

};

structItemState

{

ItemState();

boolIsSameState(constItemState&state)const;

voidPrintStates();

boolIsFinalState();

LOCATIONfarmer,wolf,sheep,vegetable;

ACTIONcurAction;

};

structActionProcess

{

ACTIONact_name;

std::functionTakeAction;

};

std::maplocationMap={

{LOCATION::LEFT,"Left"},

{LOCATION::RIGHT,"Right"}

};

std::mapactMsgMap={

{ACTION::GO_SELF,"Farmergoovertheriver"},

{ACTION::GO_WITH_WOLF,"Farmertakewolfgoovertheriver"},

{ACTION::GO_WITH_SHEEP,"Farmertakesheepgoovertheriver"},

{ACTION::GO_WITH_VEGETABLE,"Farmertakevegetablegoovertheriver"},

{ACTION::BACK_SELF,"Farmergoback"},

{ACTION::BACK_WITH_WOLF,"Farmertakewolfgoback"},

{ACTION::BACK_WITH_SHEEP,"Farmertakesheepgoback"},

{ACTION::BACK_WITH_VEGETABLE,"Farmertakevegetablegoback"},

{ACTION::INVALID,""}

};

ItemState::ItemState()

{

farmer=LOCATION::LEFT;

wolf=LOCATION::LEFT;

sheep=LOCATION::LEFT;

vegetable=LOCATION::LEFT;

curAction=ACTION::INVALID;

}

boolItemState::IsSameState(constItemState&state)const

{

return((farmer==)

&&(wolf==)

&&(sheep==)

&&(vegetable==ble));

}

voidItemState::PrintStates()

{

std::cout<

std::cout<<":"<<"framer"<

",wolf"<

",sheep"<

",vegetable"<

}

boolItemState::IsFinalState()

{

return((farmer==LOCATION::RIGHT)

&&(wolf==LOCATION::RIGHT)

&&(sheep==LOCATION::RIGHT)

&&(vegetable==LOCATION::RIGHT));

}

boolIsProcesdState(deque&states,constItemState&newState)

{

autoit=find_if((),(),

[&newState](ItemState&item){State(newState);});

return(it!=());

}

voidPrintResult(deque&states)

{

cout<<"FindResult:"<

for(auto&x:states)

{

tates();

}

cout<

}

boolIsCurrentStateValid(constItemState¤t)

{

if((==)&&(!=))

{

returnfal;

}

if((ble==)&&(!=))

{

returnfal;

}

returntrue;

}

boolProcessFarmerGo(constItemState¤t,ItemState&next)

{

if(!=LOCATION::LEFT)

returnfal;

returnfal;

next=current;

=LOCATION::RIGHT;

ion=ACTION::GO_SELF;

returnIsCurrentStateValid(next);

}

boolProcessFarmerGoTakeWolf(constItemState¤t,ItemState&next)

{

if((!=LOCATION::LEFT)||(!=LOCATION::LEFT))

returnfal;

next=current;

=LOCATION::RIGHT;

=LOCATION::RIGHT;

ion=ACTION::GO_WITH_WOLF;

returnIsCurrentStateValid(next);

}

boolProcessFarmerGoTakeSheep(constItemState¤t,ItemState&next)

{

if((!=LOCATION::LEFT)||(!=LOCATION::LEFT))

returnfal;

next=current;

=LOCATION::RIGHT;

=LOCATION::RIGHT;

ion=ACTION::GO_WITH_SHEEP;

returnIsCurrentStateValid(next);

}

boolProcessFarmerGoTakeVegetable(constItemState¤t,ItemState&next)

{

if((!=LOCATION::LEFT)||(ble!=LOCATION::LEFT))

returnfal;

next=current;

=LOCATION::RIGHT;

ble=LOCATION::RIGHT;

ion=ACTION::GO_WITH_VEGETABLE;

returnIsCurrentStateValid(next);

}

boolProcessFarmerBack(constItemState¤t,ItemState&next)

{

if(!=LOCATION::RIGHT)

returnfal;

next=current;

=LOCATION::LEFT;

ion=ACTION::BACK_SELF;

returnIsCurrentStateValid(next);

}

boolProcessFarmerBackTakeWolf(constItemState¤t,ItemState&next)

boolProcessFarmerBackTakeWolf(constItemState¤t,ItemState&next)

{

if((!=LOCATION::RIGHT)||(!=LOCATION::RIGHT))

returnfal;

next=current;

=LOCATION::LEFT;

=LOCATION::LEFT;

ion=ACTION::BACK_WITH_WOLF;

returnIsCurrentStateValid(next);

}

boolProcessFarmerBackTakeSheep(constItemState¤t,ItemState&next)

{

if((!=LOCATION::RIGHT)||(!=LOCATION::RIGHT))

returnfal;

next=current;

=LOCATION::LEFT;

=LOCATION::LEFT;

ion=ACTION::BACK_WITH_SHEEP;

returnIsCurrentStateValid(next);

}

boolProcessFarmerBackTakeVegetable(constItemState¤t,ItemState&next)

{

if((!=LOCATION::RIGHT)||(ble!=LOCATION::RIGHT))

returnfal;

next=current;

=LOCATION::LEFT;

ble=LOCATION::LEFT;

ion=ACTION::BACK_WITH_VEGETABLE;

returnIsCurrentStateValid(next);

}

ActionProcessactMap[]=

{

{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}

};

voidSearchStates(deque&states)

{

ItemStatecurrent=();/*每次都从当前状态开始*/

if(lState())

{

PrintResult(states);

return;

}

ItemStatenext;

for(auto&act:actMap)

{

{

if(tion(current,next))

{

if(!IsProcesdState(states,next))

{

_back(next);

SearchStates(states);

_back();

}

}

}

}

intmain(intargc,char*argv[])

{

dequestates;

//ItemStateinit={LOCATION::LEFT,LOCATION::LEFT,LOCATION::LEFT,LOCATION::LEFT};

ItemStateinit;

_back(init);

SearchStates(states);

asrt(()==1);/*穷举结束后states应该还是只有⼀个初始状态*/

return0;

}