农夫过河问题 matlab,农夫过河问题 宽搜（bfs）算法详解

农夫过河问题(农夫、狼、羊和白菜的问题)，描述如下：

一个农夫，带着一只狼、一只羊、和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。农夫的面前有一条小船，船小到只能容下他和一件物件。另外，只能农夫会撑船。又因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜而自己离开，也不能留下狼和羊而自己离开。但狼属于食肉动物，不吃白菜。

问农夫采取什么方案才能将所有的东西运过河？

解题思路

农夫过河问题的求解方法是使用要实现广度优先搜索，一般采用把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别对其进行处理，处理过程中再把下一步的状态放在队列里。

在采用编程解决农夫过河的问题时，首先需要考虑以下几个问题：

程序中为了方便描述农夫过河过程中几个角色的位置(位于南岸还是北岸)，最好的方法是用 4 个二进制数，分别

为了方便获取各个角色当前所在的位置，程序中设置了如下 4 个函数。其中，函数返回值为 1，反之则表示角色在河的北岸：

//表示农夫状态的函数，返回0 ，表示农夫在南岸，反之在北岸。

int farmer(int location){

return(0!=(location & 0x08));

}

//表示狼的状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int wolf(int location){

return(0!=(location & 0x04));

}

//表示白菜状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int cabbage(int location){

return(0!=(location & 0x02));

}

//表示羊状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int goat(int location){

return(0!=(location & 0x01));

}

其中，location 为当前 4 种角色所处的状态，其值为 0(0000) 到 15(1111) 之间的数。通过 location 与不同角色二进制的按位与运算，可获得当前状态下各个角色的位置。

任何角色移动后，都需要进行判断：当前移动是否是有问题的。例如，当农夫不在的情况下，是否狼和羊同时在一起，又或是羊和白菜同时在一起，这两种情况都是不安全的。所以该函数应该写为：

//判断当前状态是否合理的函数

int safe(int location){

//如果农夫不在羊身边，而羊和白菜在一起，则为不安全

if(goat(location) == cabbage(location) && goat(location) != farmer(location)){

return 0;

}

//如果农夫不在狼身边，而狼和羊在一起，也不安全

if(goat(location) == wolf(location) && goat(location) != farmer(location)){

return 0;

}

//其他情况都安全

return 1;

}

为了记录各个角色的移动过程，程序中设置了

初始状态下，route 中的每个分量都为 -1，每当在队列中加入一个新状态时，就把数组中与该状态对应的位置的值改为达到此状态的前一状态的下标值。即此位置存储上一状态所在位置的下标(便于最后输出整个的移动方案)。在route数组中，一个元素具有非负值，表明这个状态已被访问过。

解决以上 4 个难题，农夫过河的问题就很简单了，实现代码如下：

#include

#include

#define MAXSIZE 100 //队列的最大长度

typedef int ElemType;

typedef struct{

ElemType data[MAXSIZE];//队列的存储空间

int front,rear;//队列的队头指针和队尾指针

}SqQueue;

//初始化队列

void Init_SqQueue(SqQueue *Q){

Q->front = Q->rear =0;

}

//判断队列是否为空

int Empty_SqQueue(SqQueue *Q){

return Q->rear == Q->front;//为真，返回1 则表示队列为空

}

//数据 e 进队列

void In_SqQueue(SqQueue *Q, int e){

if(Q->rear == MAXSIZE){

return;

}

Q->data[Q->rear] = e;

Q->rear+=1;

}

//数据出队列，通过将出队列数据赋值给 e

void Out_SqQueue(SqQueue *Q,int *e){

//出队之前，先判断队列是否为空

if(Q->rear == Q->front){

return;

}

*e = Q->data[Q->front];

Q->front+=1;

}

//表示农夫状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int farmer(int location){

return(0!=(location & 0x08));

}

//表示狼的状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int wolf(int location){

return(0!=(location & 0x04));

}

//表示白菜状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int cabbage(int location){

return(0!=(location & 0x02));

}

//表示羊状态的函数，返回0 ，表示农夫在南岸，反之在北岸

int goat(int location){

return(0!=(location & 0x01));

}

//判断当前状态是否合理的函数

int safe(int location){

//如果农夫不在羊身边，而羊和白菜在一起，则为不安全

if(goat(location) == cabbage(location) && goat(location) != farmer(location)){

return 0;

}

//如果农夫不在狼身边，而狼和羊在一起，也不安全

if(goat(location) == wolf(location) && goat(location) != farmer(location)){

return 0;

}

//其他情况都安全

return 1;

}

//农夫过河的实现函数

void farmerproblem(){

int movers,location,newlocation;

int route[16];//用于记录已考虑的状态路径

int i;

SqQueue moveto;

Init_SqQueue(&moveto);

//以所有角色都在南岸开始

In_SqQueue(&moveto,0x00);

//对记录路径的数组初始化

for(i=0;i<16;i++){

route[i] = -1;

}

//记录所有角色都在南岸的路径

route[0] = 0;

while(!Empty_SqQueue(&moveto) && (route[15] == -1)){

Out_SqQueue(&moveto,&location);//出队列，并将状态赋值给location

//依次移动羊、白菜、狼和农夫，movers每次左移一位，所以其值每次为1,2,4,8

for(movers =1;movers<=8;movers<<=1){

//判断农夫与要移动的角色是否位于河岸的同一侧

if(((location & 0x08)!=0) == ((location & movers)!=0)){

//若农夫与该角色在同一侧则尝试移至对岸(异或运算)

newlocation = location^(0x08|movers);

//判断此移动是否安全

if(safe(newlocation) && route[newlocation] == -1){

//如果安全，且之前没有移动过，则进行记录，记录方法是在新位置记录之前的移动位置

route[newlocation] = location;

//将新的移动方案入队

In_SqQueue(&moveto , newlocation);

}

}

}

}

//如果最终移动成功，即由 0000 变成 1111则视为成功

if(route[15]!=-1){

printf("the reverse path is :");

for(i=15; i>=0; i=route[i]){

printf("n the location is:%d",i);

if(i==0){

break;

}

}

}else{

printf("no path");

}

}

int main(){

farmerproblem();

return 0;

}

运行结果为：

the reverse path is :

the location is:15

the location is:6

the location is:14

the location is:2

the location is:11

the location is:1

the location is:9

the location is:0

提示：输出的各个数字，要转化为二进制看，才有意义，例如，15，二进制为1111，表示农夫、狼、白菜和羊都在河的北岸；而最终的 0，二进制为 0000，表示其都在南岸。