实验：农夫狼羊和菜问题

1、实验 6 ：农夫、狼、羊和菜问题一、实验目的：1. 会定义图的抽象数据类型；2. 熟悉图的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相 互关系及各自的作用；3. 熟悉对图的一些基本操作和具体的函数定义；4. 掌握在实际问题中运用所学知识解决实际问题的方法和步骤。二、实验内容描述：有一农夫带着一条狼、 一只羊和一筐菜， 想从河的左岸乘船到右岸。 但由于船太 小，农夫每次只能带一样东西过河，而且，如果没有农夫看管，则狼会吃羊，羊 会吃菜。问农夫怎样过河才能把每样东西安全地送过河。三、实验要求：1. 将上述问题用图表示出来；2. 选择图的一种存储结构，编写一个自动生成该图的算法；3.

2、在上述基础上编写求解该问题的算法程序，并用此程序上机运行、调试，4. 屏幕显示结果，能结合程序进行分析。四、问题分析：该问题从表面上看， 并不是一个图的问题， 但可以把它用图表示出来， 从而 转换为一个图的问题。 在这个问题的解决过程中， 农夫需要多次架船往返于两岸 之间，每次可以带一样东西或者自己单独过河，每一次过河都会使农夫、狼、羊 和菜所处的位置发生变化。如果用一个四元组( Farmer,Wolf,Sheep,Veget )表 示当前农夫、狼、羊和菜所处的位置，其中每个元素可以是 0 或 1，0 表示在左 岸，1表示在右岸。这样，对这四个元素的不同取值可以构成16 种不同的状态，初始时的

3、状态则为( 0，0，0， 0)，最终要达到的目标为( 1，1，1，1)。状态之 间的转换可以有下面四种情况：(1)农夫不带任何东西过河，可表示为： (Farmer,Wolf,Sheep,Veget) (!Farmer,Wolf,Sheep,Veget) ( 2)当农夫和狼在相同位置时，表示农夫带狼过河，即当Farmer=Wolf 时：(Farmer,Wolf,Sheep,Veget) (!Farmer,!Wolf,Sheep,Veget)(3)当农夫和羊在相同位置时，表示农夫带羊过河，即当Farmer=Sheep时：(Farmer,Wolf,Sheep,Veget) (!Farmer,Wolf

4、,!Sheep,Veget)(4)当农夫和菜在相同位置时，表示农夫带菜过河，即当Farmer=Veget时：(Farmer,Wolf,Sheep,Veget) (!Farmer,Wolf,Sheep,!Veget)在这16种状态中，有些状态是不安全的，是不允许出现的，如(1,1, 0, 0)表示农夫和狼在右岸，而羊和菜在左岸，这样羊会吃掉菜。如果从16种状态中删去这些不安全状态，将剩余的安全状态之间根据上面的转换关系连接起来，就得到如下图所示的图。图1农夫、狼、羊和菜问题的状态图这样，原始问题就转换为在这个图中寻找一条从顶点(0，0，0，0)到顶点(1, 1，1，1 )的路径的问题。五、存储结

5、构：采用邻接矩阵和邻接表都可以完成求图中两顶点间的路径问题，这里，我们不妨采用邻接矩阵存储结构。其中图的每个顶点结点包括四个域，类型定义为：typedef struct/*定义图的顶点类型*/int Farmer,Wolf,Sheep,Veget;VexType;图的邻接矩阵存储结构定义为：#define VEX-NUM 10/*最大顶点个数 */typedef structint vexnum,e; /*VexType vexVEX-NUM;int adjVEX-NUMVEX-NUM;/*图的当前顶点数和边数 */顶点向量 */* 邻接矩阵 */AdjGraph;具体方法是先生成各种安六、算

6、法思想 ： 在这个问题中， 首先需要自动生成图的邻接矩阵存储， 全状态结点，存放在顶点向量中； 再根据状态之间的转换关系形成顶点之间的所 有边，保存在邻接矩阵中。 在建立了图的邻接矩阵存储结构后， 利用深度优先搜 索思想求出从顶点（ 0，0，0，0）到顶点（ 1，1，1，1）的一条简单路径七、实验程序：#include<stdio.h>#define VEX_NUM 10typedef enumFALSE,TRUEBoolean;typedef structint Farmer,Wolf,Sheep,Veget;VexType;typedef structint vexnum,e;

7、VexType vexsVEX_NUM;int adjVEX_NUMVEX_NUM;AdjGraph;Boolean visitedVEX_NUM;int pathVEX_NUM;int locate(AdjGraph*G,int F,int W,int S,int V) int i;for(i=0;i<G->vexnum;i+)if(G->vexsi.Farmer=F&&G->vexsi.Wolf=W&&G->vexsi.Sheep=S&&G-> vexsi.Veget=V)return(i);return(

8、-1);int is_safe(int F,int W,int S,int V)if(F!=S&&(W=S|S=V)return(0);elsereturn(1);int is_connected(AdjGraph*G,int i,int j)int k;k=0;if(G->vexsi.Wolf!=G->vexsj.Wolf)k+;if(G->vexsi.Sheep!=G->vexsj.Sheep)k+;if(G->vexsi.Veget!=G->vexsj.Veget)k+;if(G->vexsi.Farmer!=G->vexs

9、j.Farmer&&k<=1)return(1);elsereturn(0);void CreateG(AdjGraph*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->vexsi.Farmer=F;G->vexsi.Wolf=W;G->vexsi.Sheep=S;G->vexsi.Veget=V;i+;G->vexnum=i;for(i=0;

10、i<G->vexnum;i+) for(j=0;j<G->vexnum;j+) if(is_connected(G,i,j) G->adjij=G->adjij=1; elseG->adjij=G->adjji=0; return;void print_path(AdjGraph*G,int u,int v) int k;k=u;while(k!=v)printf("(%d,%d,%d,%d)n",G->vexsk.Farmer,G->vexsk.Wolf,G->vexsk .Sheep,G->vexs

11、k.Veget);k=pathk;printf("(%d,%d,%d,%d )n",G->vexsk.Farmer,G->vexsk.Wolf,G->vexsk.Sheep,G->vexsk.Veget);void DFS_path(AdjGraph*G,int u,int v)int j;visitedu=TRUE;for(j=0;j<G->vexnum;j+)if(G->adjuj&&!visitedj&&!visitedv)pathu=j;DFS_path(G,j,v);void main()int i,j;AdjGraph graph;CreateG(&graph);for(i=0;i<graph.vexnum;i+)visitedi=FALSE;i=locate(&graph,0,0,0,0);j=locate(&graph,1,1,1,1);DFS_path(&graph,i,j); if(v