农夫过河的四种解法 - Touch的博客 - ITeye技术网站
博客分类：
* 题目描述：有一个农夫，带着一只狼、一只羊、一颗白菜过河。其中农夫不在的时候狼会吃羊，
羊会吃白菜。只有一只船，且每次农夫最多只能带一样物品过河。求解决方案。
* 思路：1. 过程回溯法。把人、狼、羊、白菜看成A、B、C、D。过河的时候从ABCD中选两个过河，在
选一个回来。若发生狼跟羊、羊跟白菜在同一个岸边，且农夫不在场，则回溯.
2. 图的遍历。设从南岸到北岸，在南岸ABCD的各个状态是（用二进制表示）：0000，在
北岸的时候各个状态是：1111。所以过河问题就是从0000起始状态到1111最终状态的
过程。易得，总共有16中状态。然后把每一种状态看成图的一个结点，把可以连通的
结点用有向边连起来，就构成的一个有向图。从0000这个结点遍历（深度优先或者广
度优先）图，遍历到1111结点则找到解。
3. 状态回溯法。设从南岸到北岸，在南岸ABCD的各个状态是（用二进制表示）：0000，在
北岸的时候各个状态是：1111。所以过河问题就是从0000起始状态到1111最终状态的
过程。易得，总共有16中状态。从第一种状态0000开始搜索，搜索当前状态下可以到达的
状态，搜索到一个则把这个状态看成当前状态，继续搜索。若出现当前状态搜索无可到达
的状态或已遍历所有搜索出来的状态，则回溯。直到到达1111状态。
4. 状态队列搜索法。跟思路3类似，只是搜索的方式不一样。思路3中用栈的思想进行深度搜索
这里采用队列的思想进行广度搜索。
Touch_2011
浏览: 139381 次
来自: 武汉
大侠，你这个程序的递归部分看不懂，能不能麻烦解释一下递归的思路 ...
我是一楼的神马_CS哦 再次表示感谢！！
好 万分感谢 ！！
shenma_CS 写道你好！ 我看了你的代码 有好多让我佩服 ...
乘法是模拟数学上两个数相乘，但在处理进位方面可能有点不同。比如 ...后使用快捷导航没有帐号？
查看: 1707|回复: 1
人工智能经典农夫过河问题C语言源程序求助
一般战友, 积分 119, 距离下一级还需 381 积分
在线时间15 小时
主题帖子积分
一般战友, 积分 119, 距离下一级还需 381 积分
一般战友, 积分 119, 距离下一级还需 381 积分
#include &stdio.h&
typedef struct Seque{
char *action[50];
struct Seque *
int count1=0;
int flag=0;
void push(char action1[],int cabbage,int wolf,int sheep,int farmer,int count)
p=(Seque*)malloc(sizeof(Seque));
p-&farmer=
p-&cabbage=
strcpy(p-&action,action1);
p-&next=NULL;
rear-&next=p;
void pop()
while(q-&next!=rear)
q-&next=NULL;
void showsolution(int i)
printf(&&&methold %d:\n&,count1);
while(q-&count&=i)
&&printf(&&&%d.%s\n&,q-&count,q-&action);
void Takesheepover(int i)
char action[]=&Take the sheep over&;
push(action,rear-&cabbage,rear-&wolf,1,1,i);
void Bringsheepback(int i)
char action[]=&Bring the sheep back&;
push(action,rear-&cabbage,rear-&wolf,0,0,i);
void Takewolfover(int i)
char action[]=&Take the wolf over&;
push(action,rear-&cabbage,1,rear-&sheep,1,i);
void Bringwolfback(int i)
char action[]=&Bring the wolf back&;
push(action,rear-&cabbage,0,rear-&sheep,0,i);
void Takecabbageover(int i)
char action[]=&Take cabbage over!&;
push(action,1,rear-&wolf,rear-&sheep,1,i);
void Bringcabbageback(int i)
char action[]=&Bring the cabbage back&;
push(action,0,rear-&wolf,rear-&sheep,0,i);
void Gooveronly(int i)
char action[]=&Go over only!&;
push(action,rear-&cabbage,rear-&wolf,rear-&sheep,1,i);
void Gobackonly(int i)
char action[]=&Go back only!&;
push(action,rear-&cabbage,rear-&wolf,rear-&sheep,0,i);
void Tryonestep(int i)
& &Seque *t;
& &if(i&100)
& & if (rear-&farmer==1&&
& & & & rear-&wolf==1&&
& & & & rear-&cabbage==1&&
& & & & rear-&sheep==1)
& &&&count1++;
& &&&flag++;
& &&&showsolution(i);
& &&&printf(&&&flag=%d&,flag);
& &&&pop();
for(t=t!=t=t-&next)
& && &if((t-&farmer==rear-&farmer)&&
& & & && & (t-&wolf==rear-&wolf)&&
& & & && & (t-&cabbage==rear-&cabbage)&&
& & & && & (t-&sheep==rear-&sheep))
& & & && && & {
& & & && && & pop();
& & & && && &
& & & && && & }
& &if(((rear-&farmer!=rear-&wolf)&&
& && &(rear-&wolf==rear-&sheep))||
& && &((rear-&farmer!=rear-&sheep)&&
& && &(rear-&cabbage==rear-&sheep)))
& & pop();
& &&&if(rear-&farmer==0)
& && & Gooveronly(i);
& && & Tryonestep(i);
& && & if(rear-&wolf==0)
& & & &&&Takewolfover(i);
& & & &&&Tryonestep(i);
& && &if(rear-&sheep==0)
& & & & Takesheepover(i);
& & & & Tryonestep(i);
& && &if(rear-&cabbage==0)
& && & Takecabbageover(i);
& && & Tryonestep(i);
& && & Gobackonly(i);
& && & Tryonestep(i);
&&if(rear-&wolf==1)
& && & Bringwolfback(i);
& && & Tryonestep(i);
& & if(rear-&sheep==1)
& && & Bringsheepback(i);
& && & Tryonestep(i);
& &if(rear-&cabbage==1)
& && & Bringcabbageback(i);
& && & Tryonestep(i);
front=rear=(Seque*)malloc(sizeof(Seque)) ;
front-&farmer=0;
front-&wolf=0;
front-&cabbage=0;
front-&sheep=0;
front-&count=0;
strcpy(front-&action,&start take action!&);
front-&next=NULL;
printf(&\n&);
Tryonestep(0);
一般战友, 积分 119, 距离下一级还需 381 积分
在线时间15 小时
主题帖子积分
一般战友, 积分 119, 距离下一级还需 381 积分
一般战友, 积分 119, 距离下一级还需 381 积分
为什么输出的结果只有一种算法，
要让两种算法都输出该如何修改源程序？
您还剩5次免费下载资料的机会哦~
扫描二维码下载资料
使用手机端考研帮，进入扫一扫在“我”中打开扫一扫，扫描二维码下载资料
Powered by Discuz!问题描述
一个农夫带着一只狼，一棵白菜和一只山羊要从一条河的南岸到北岸，农夫每次只能带一样东西过过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃菜，请为农夫设计过河方案。
分析：
&&& 要求解农夫过河问题，首先要选择一个对问题中每个角色的位置进行描述的方法。用四位二进制数顺序表表示农夫、狼、白菜和羊的位置。用1表示在南岸，0表示在北岸。共有中状态，以每一种状态为图的一个顶点，判断状态中可行的点。
&&& 根据可能出现的情况创建无向图，农夫的运动状态建立邻接矩阵，确定起始状态顶点为状态0000，终结状态顶点为1111，即开始时农夫、狼、羊和白菜都在北岸，顶点状态为0000，运用递归调用深度优先遍历图，从开始状态顶点到结束状态顶点遍历，输出过河情况。
图解
部分代码分析：
以农夫，狼，羊和白菜安全的情况为顶点创建无向图。
void Graph()
{
for(int i=0;i&MaxSi++)
for(int j=0;j&MaxSj++)
fwsc[i][j]=0;
for(int farmer=0;farmer&=1;farmer++)
{
for(int wolf=0;wolf&2;wolf++)
{
for(int sheep=0;sheep&2;sheep++)
{
for(int cabbage=0;cabbage&2;cabbage++)
{
if(isSafety(farmer,wolf,sheep,cabbage))
{ k++;
for(int i=k-1;i&k;i++)
vertex[i]=8*farmer+4*wolf+2*sheep+1*
for(int i=0;i&k;i++)
{
for(int j=0;j&k;j++)
{
fwsc[i][j]=1;
fwsc[j][i]=1;
}}}}}}}}深度遍历无向图，并调用递给算法前面
参看
看完这些多多尝试自己去实现，确实这个问题当初我也是搞了几天才想明白的，实在不会写的话看源码（c语言实现）
#include "stdio.h"
#include"stdlib.h"
#define MaxVerNum 16 //最大顶点数
int visited[MaxVerNum]; //对已访问的顶点标记
int path[MaxVerNum]; //保存DFS搜索到的路径，即与某顶点到下一顶点的路径
int l=1;
typedef struct
{
typedef struct
{
VextexType vexs[MaxVerNum]; //顶点表
intedges[MaxVerNum][MaxVerNum]; //邻接矩阵，即边表
//顶点数
}MG //MGraph是以邻接矩阵存储的图类型
int locate(MGraph *G,int F,int W,int S,int V) //查找顶点（F,W,S,V）在顶点向量中的位置
{
for(i=0;i&G-&n;i++)
if(G-&vexs[i].farmer==F&&G-&vexs[i].wolf==W&&G-&vexs[i].sheep==S&&G-&vexs[i].vegetable==V)
return (i); //返回当前位置
return (-1); //没有找到此顶点
}
int is_safe(int F,int W,int S,int V) //判断状态是否安全
{
if(F!=S&&(W==S||S==V)) return 0; //当农夫与羊不在一起，并且狼和羊，羊和菜在一起的时候是不安全的
else return 1;
}
int is_connected(MGraph *G,int i,int j) //判断状态i和j之间是否连通
{
if(G-&vexs[i].wolf!=G-&vexs[j].wolf) k++;
if(G-&vexs[i].sheep!=G-&vexs[j].sheep) k++;
if(G-&vexs[i].vegetable!=G-&vexs[j].vegetable) k++;
if(G-&vexs[i].farmer!=G-&vexs[j].farmer&&k&=1)
return 1; //以上三个条件不同时满足且农夫状态改变时，返回真，即农夫每次只能带一件东西过船
else return 0;
}
void CreateG(MGraph *G)
{
int i,j,F,W,S,V;
i=0; //生成所有安全的图的顶点
for(F=0;F&=1;F++)
for(W=0;W&=1;W++)
for(S=0;S&=1;S++)
for(V=0;V&=1;V++)
if(is_safe(F,W,S,V))
G-&vexs[i].farmer=F;
G-&vexs[i].wolf=W;
G-&vexs[i].sheep=S;
G-&vexs[i].vegetable=V;
for(i=0;i&G-&n;i++)
for(j=0;j&G-&n;j++)
if(is_connected(G,i,j)) //状态i与j之间可以转化，初始化为1，否则为0
G-&edges[i][j]=G-&edges[j][i]=1;
G-&edges[i][j]=G-&edges[j][i]=0;
// return 1;
}
void move(MGraph *G,int k,int j) //状态的文字说明
{
if(G-&vexs[k].wolf!=G-&vexs[j].wolf) printf("带狼");
else if(G-&vexs[k].sheep!=G-&vexs[j].sheep) printf("带羊");
else if(G-&vexs[k].vegetable!=G-&vexs[j].vegetable) printf("带白菜");
else printf("自己");
}
void print_path(MGraph *G,int u,int v) //输出从u到v之间的简单路径，即顶点序列中不重复的路径
{
int k,p=1,t=1,j;
k=u;
printf("第%d种方法：\n",l++);
while(k!=v)
j=k;
k=path[k];
printf("\t第%d步:\n",p);
printf("\t(%d,%d,%d,%d)",G-&vexs[k].farmer,G-&vexs[k].wolf,G-&vexs[k].sheep,G-&vexs[k].vegetable);
printf("农夫");
move(G,k,j);
if(t%2==1) printf("到北岸\n");
else printf("到南岸\n");
void DFS_path(MGraph *G,int u,int v) //深度优先搜素从u到v的简单路径
{
visited[u]=1; //标记已访问过的点
for(j=0;j&G-&n;j++)
{
if(G-&edges[u][j]&&visited[j]==0)
path[u]=j;
DFS_path(G,j,v);
if(j==v) print_path(G,0,9);
}
visited[u]--;
void main()
{
CreateG(&graph);
for(i=0;i&graph.n;i++) visited[i]=0; //置初值
i=locate(&graph,0,0,0,0);
j=locate(&graph,1,1,1,1);
DFS_path(&graph,i,j);
文章来源：原创文章版权为网站和作者共同所有，会员文章禁止转载。非会员文章转载做好本文超链接即表示授权转载。通过文章下面的分享按钮可以自由分享所有文章。
当前位置：-> ->上一篇：下一篇：
在线提问 问题标题： 问题描述：(简陋的描述会导致问题被最后回答、没有针对性回答甚至无法解答。请确保问题描述的足够清楚。)
弹幕群聊(QQ群:)本帖子已过去太久远了，不再提供回复功能。