农夫过河

程序设计报告

题目：农夫过河

专 业：计算机科学与技术

小组成员：

班 级:

指导教师：

日 期：2014年12月25日

成员分工：

农夫过河

【摘要】

农夫问题即一个农民带着一只狼、一只羊和一棵白菜，身处河的南岸,他需要把这些东西全部运到河的北岸。而他只有一条小船，且这只小船小到只能容下他和一件物品,另外只有农民能撑船。农夫不能留下狼和羊自己离开，也不能留下白菜和羊自己离开,更不能留下狼，羊和白菜而独自离开，因为没有农夫的照看,狼就要吃掉羊,而羊又要吃掉白菜。好在狼是是肉动物，它不吃白菜，问农夫应该采取什么方案才能将所有的东西安全地从河的南岸运到北岸？这类农夫问题是一个传统的数据结构问题,利用基于队列的图的广度优先搜索求解农夫过河问题是一个易于理解、切实可行的方案,具有一定的推广价值。

关键字：农夫过河问题;队列;广度优先搜索

一、 实验内容概述(设计任务与技术要求)

农民过河问题是指农民需要带一只狼、一只羊和一棵白菜到河的南岸去,需要安全运到北岸。而一条小船只能容下他和一件物品,只有农民能撑船。问农民怎么能安全过河,问题中需要涉及到狼会吃羊,羊会吃白菜,所以农民不能将这两种或三种物品单独放在河的一侧,因为没有农民的照看,狼就要吃掉羊,而羊可能又要吃掉白菜。 这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。

根据实际情况，对此问题分析可以得到不同的特征：

1,是农民和羊在河的南岸，狼和白菜在河的北岸；

2,是从一个状态可转到另外一个状态，而不违反狼吃羊，羊吃草的规则（例如农民自己过河或者农民带着羊过河）；

3,是有些状态是不安全的（例如农民一人在北岸，而其他的东西都在南岸）；

4,是初始状态是农民，羊，狼，白菜都在河的南岸和结束状态是农民，羊，狼，白菜都在河的北岸。

实现农夫过河问题，则需要找到一条合法的路径（相邻状态之间的转移合法），从开始状态到某个结束状态，路途中不能经过不安全的状态。

二、 实验目的概述(总体设计方案)

a ) 利用图的有关知识来解决农夫过河问题

b ) 根据图的广度（深度）优先搜索来实现实验要求

在实施此问题中，首先要为农夫，狼，白菜和羊设置求状态的函数，若某一种物品在河的南岸，则返回0，若在河的的北岸，则返回1；其次是为每一种状态做测试，状态安全则返1，否则返回0。

三、 解题思路的描述(数据结构和算法的设计)：

农夫过河问题根据图求解的搜索过程可采用两种不同的策略：一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。则我在此实验中，采取的是利用广度优先搜索来解决农夫问题。

算法中要先各为农夫，狼，白菜和羊设置参数，这可以用枚举类型为各种物品设置参数，其中羊goat=0001,白菜cabbage=0010，狼wolf=0100,农民farmer=1000，而且利用moveTo来记录可到的尚未向前测试的状态，数据元素route[i]来记录状态i的路径[前一状态]，如果是-1，则表示尚未访问。

算法的总体思想为：

{

初始化顺序表Route和安全队列moveTo

初始安全状态0（0000）入队列moveTo,Route[0]=0

While(IsEmpty(moveTo)&&(route[15]==-1))

{

OutQuere(moveTo,location); //出队当前安全状态

for(每个从location可以过渡到得状态newlocation) //农夫(附带同侧物品)移动

if(newlocation安全且未访问过)

OutQueue(moveTo,newlocation);

}

if(route[15]!=-1 //已经到达终点了，打印路径

for(location=15;location>=0;location=route[location]

{

printf (“The location is : %dn",location);

if(location==0) return 1;return 1;

}

else

printf(“无解！\n");

}

在程序中涉及了很多的状态，共有16种，从高位到低位分别表示农夫，狼，白菜和羊，如果是0000则表示农夫，狼，白菜和羊都在南岸，1111表示都到达了北岸。其他的状态则分别表示：

0001表示羊在北岸 0010表示白菜在北岸

0011表示羊和白菜在北岸 0100表示狼在北岸

0101表示狼和羊在北岸 0110表示狼和白菜北岸

0111表示狼，白菜和羊在北岸 1000表示农夫和北岸

1001表示农夫，羊在北岸 1010表示农夫，白菜在北岸

1011表示农夫，白菜和羊在北岸 1100表示农夫，狼在北岸

1101表示农夫，狼和羊在北岸 1110表示农夫，狼和白菜在北岸

其中有些状态是不允许出现的，有0011，0101，0111，0001，1100，1001，因为这些状态是不安全的，所以可以为以上的条件绘制体统的状态图。

四 算法的精化

用一个整数队列moveto，把搜索过程中的每一步所有可能达到的状态都保存起来都保存起来。队列中每一个元素表示一个可以安全到达的中间状态。另外，用一个整数数组route，用于记录已被访问过的各个状态，以及已被发现的能够到达这些状态的前驱状态。Route数组只需使用16个元素。ROUTE的每一个元素初始化值均设置为负一，每当在队列加入一个新状态时，就把route中以该状态做下标的元素的值改为达到这个状态的前一状态的下标值。所以，这数组的第i个元素，不仅记录状态i是否已被访问过，同时对已被访问过的状态，还保存了这个状态的前驱状态下的下标。算法结束后可以利用route数组元素的值生成一个正确的状态路径。

五 程序代码

#include

#include

#define QUEUE_INIT_SIZE 100

#define QUEUE_INC 50

typedef int ElemType;

typedef struct

{

ElemType *data; /* 动态分配存储空间*/

int queuesize;

int front; /*头指针，若队列不空，指向队列头元素*/

int rear; /*尾指针，若队列不空，指向队列尾元素*/

} SqQueue;

bool InitQueue(SqQueue &Q) //构造队列

{

Q.data = (ElemType *)malloc(QUEUE_INIT_SIZE*sizeof(ElemType));

if(!Q.data )

return false;

Q.front = 0; Q.rear = 0; Q.queuesize = QUEUE_INIT_SIZE;

}

bool DestroyQueue(SqQueue &Q) //销毁队列

{

if(Q.data)

{

free(Q.data);

Q.data = NULL;

}

return true;

}

void ClearQueue(SqQueue &Q) //清空队列

{

Q.front = 0; Q.rear = 0;

}

bool QueueEmpty(SqQueue Q) //

{

return Q.front==Q.rear ;

}

bool GetHead(SqQueue Q,ElemType &e)

{

if(Q.front==Q.rear) return false;

e = Q.data[0];

return true;

}

bool EnQueue(SqQueue &Q,ElemType e) //插入元素e,为Q的新的队尾元素

{

if((Q.rear+1)%Q.queuesize==Q.front)

{ /*队列满*/

return false;

}

Q.data[Q.rear] = e;

Q.rear = (Q.rear+1)%Q.queuesize;

return true;

}

bool OutQueue(SqQueue &Q,ElemType &e)

{

if(Q.front==Q.rear)

return false;

e=Q.data[Q.front];

Q.front = (Q.front+1)%Q.queuesize;

return true;

}

int safe(int location);

int farmerProblem( )

{

int movers, i,location, newlocation;

int route[16]; /*记录已考察的状态路径*/

for(i=0;i<16;i++) //将所有情况先设为未访问

route[i]=-1;

SqQueue moveTo;

InitQueue(moveTo);

EnQueue(moveTo,0x00); /*准备初值（队尾元素）*/

route[0]=0;

while(!QueueEmpty(moveTo)&&(route[15]==-1))

{

OutQueue(moveTo,location); /*得到现在的状态*/

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

{ /* 农民总是在移动，随农民移动的也只能是在农民同侧的东西 */

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

{

newlocation=location^(0x08|movers);

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

{

route[newlocation]=location; /*记录路径*/

EnQueue(moveTo,newlocation); /*压入队列*/

}

}

}

}

if(route[15]!=-1)

{

printf("0001-goat，0010-cabbage，0100-wolf，1000-farmer \n");

printf("The reverse path is : \n");

for(location=15;location>=0;location=route[location])

{

printf("The location is : %d\n",location);

if(location==0)

return 1;

}

}

else printf("No solution.\n");

return 0;

}

int main()

{

farmerProblem();

}

int farmer(int location) /*为农民设置参数8*/

{

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

}

int wolf(int location) /*为狼设置参数4*/

{

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

}

int cabbage(int location) /*为白菜设置参数2*/

{

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

}

int goat(int location) /*为羊设置参数1*/

{

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

}

int safe(int location) /* 为每种状态做测试，状态安全则返回1，否则返回0*/

{ /*安全性判断函数，安全则返回1*/

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

return (0); /* 羊和白菜在河的一侧且人不在，则羊就要吃白菜*/

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

return (0); /* 狼和羊在河的一侧且人不在，则狼就要吃羊*/

return (1); /* 其他状态是安全的*/

}

六、程序调试及测试结果

将其转化为二进制就得到完整的农民过河的整个方案：

农民把羊带到北岸(0000 - 1001)

农民独自回到南岸(1001 - 0001)

农民把白菜带到北岸(0001 - 1011)

农民带着羊返回南岸(1011 - 0010)

农民把狼带到北岸(0010 - 1110)

农民独自返回南岸(1110 - 0110)

农民把羊带到北岸(0110 - 1111)

七 结论

在这过程中，我们学会了实际动手能力和独立思考的能力，我们小组团结协作，虽然困难重重，但我们还是通过查阅书籍和网络，还有身边同学的帮助解决了，我们相信我们可以将这次所学到的知识和技巧运用到以后的编程中。通过这次程序设计，我们有了一定的编程经验，并运用了所学的知识，将老师上课讲的知识运用到实践中，虽然这次程序设计用掉了我们很多的时间，但在辛苦中我们体会到了编程的快乐，并在协作中锐意进取。本方案有个地方可以再改进，就是在农民花费的问题上，可以将图形改为有向图，然后为每边加上一个花费的权值，最后就可以求得在所有的初始态到终态的路径中，取出一条最短的路径。

根据广度优先搜索的思想，还可以解决布线迷宫问题和分油问题，当然这需要对程序进行适当的修改，但是总体的思想可以互相运用。

参考文献：C语言版数据结构 清华大学出版社

计算机算法设计与分析 电子工业出版社

C语言程序设计第四版 清华大学出版社

本文来源：https://www.2haoxitong.net/k/doc/d886d3543186bceb19e8bbc3.html