更新时间：2015-12-01 21:35:25浏览次数：1+次
问题描述
一个农夫带着一只狼，一棵白菜和一只山羊要从一条河的南岸到北岸，农夫每次只能带一样东西过过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃菜，请为农夫设计过河方案。
分析：
要求解农夫过河问题，首先要选择一个对问题中每个角色的位置进行描述的方法。用四位二进制数顺序表表示农夫、狼、白菜和羊的位置。用1表示在南岸，0表示在北岸。共有0000~1111中状态，以每一种状态为图的一个顶点，判断状态中可行的点。
根据可能出现的情况创建无向图，农夫的运动状态建立邻接矩阵，确定起始状态顶点为状态0000，终结状态顶点为1111，即开始时农夫、狼、羊和白菜都在北岸，顶点状态为0000，运用递归调用深度优先遍历图，从开始状态顶点到结束状态顶点遍历，输出过河情况。
图解
部分代码分析：
以农夫，狼，羊和白菜安全的情况为顶点创建无向图。
void Graph()
{
for(int i=0;i<MaxSize;i++)
for(int j=0;j<MaxSize;j++)
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*cabbage;
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
{
int farmer;
int wolf;
int sheep;
int vegetable;
}VextexType;
typedef struct
{
VextexType vexs[MaxVerNum]; //顶点表
int edges[MaxVerNum][MaxVerNum]; //邻接矩阵，即边表
int n; //顶点数
}MGraph; //MGraph是以邻接矩阵存储的图类型
int locate(MGraph *G,int F,int W,int S,int V) //查找顶点（F,W,S,V）在顶点向量中的位置
{
int i;
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之间是否连通
{
int k=0;
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;
i++;
}
G->n=i;
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;
else
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");
p++;
t++;
}
}
void DFS_path(MGraph *G,int u,int v) //深度优先搜素从u到v的简单路径
{
int j=0;
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()
{
int i,j;
MGraph graph;
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);
}
相关资讯
