农夫携物过河程序

1、题目内容：有一农夫要将自己的羊、蔬菜和狼等3件物品运过河。但农夫过河时所用的船每次最多只能装其中的一件物品，而这3件物品之间又存在一定的制约关系：羊不能单独和狼以及不能和蔬菜在一起，因为狼要吃羊，羊也能吃蔬菜。试构造出问题模式以编程实现这一问题的求解。1、 问题分析和任务定义：根据对象的状态分为过河（1）和不过河（0），此对象集合就构成了一个状态空间。问题就是在这个状态空间内搜索一条从开始状态到结束状态的安全路径。显然，其初始状态为四对象都不过河，结束状态为四对象全部过河。这里用无向图来处理，并采用邻接矩阵存储。对于农夫，狼，羊，蔬菜组成一个4位向量，即图的顶点（f，w，s，v），状态空间为1

2、6，初始状态为（0000），目标为（1111）。解决问题的方法是，找到所有的安全状态，并在其中搜索出一条（0000）到（1111）的路径。对当前对象是否安全的判断，若当农夫与羊不在一起时，狼与羊或羊与蔬菜在一起是不安全的，其他情况是安全的。搜索一条可行路径时，采用深度优先搜索dfs_path，每个时刻探索一条路径，并记录访问过的合法状态，一直向前探视，直到走不通时回溯。显然，应该用数组来保存访问过的状态，以便回溯。显然农夫每次状态都在改变，最多也就能带一件东西过河，故搜索条件是，在顶点（f，w，s，v）的转换中，狼，羊，蔬菜三者的状态不能大于一个，即只有一个发生改变或者都不变。 数据的输入形式

3、和输入值的范围：本程序不需要输入数据，故不存在输入形式和输入值的范围。 结果的输出形式：在屏幕上显示安全状态的转换，即一条安全路径。2、 数据结构的选择概要设计数据结构的选择：本程序采用无向图处理。#define maxnumvertices 10 /最大顶点数typedef struct /图的顶点类型 int farmer,wolf,sheep,veget;/存储农夫，狼，羊，蔬菜的状态vextype;typedef struct/图的各项信息 int vertexnum,currentedges; /图的当前顶点数和边数 vextype verticeslistmaxnumvertice

4、s; /顶点向量（代表顶点） int edgemaxnumverticesmaxnumvertices;/邻接矩阵 /用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关adjgraph;为了实现上述程序的功能，需要：生成所有安全的图的顶点；查找顶点的位置；判断目前（f，w，s，v）是否安全，安全返回1，否则返回0；判断顶点i和顶点j之间是否可转换，可转换返回真，否则假；深度优先搜索从u到v的简单路径；输出从u到v的简单路径，即顶点序列中不重复出现的路径。本程序包含7个函数： 主函数main（） 生成所有安全的图的顶点函数createg（） 查找顶点位置函数locate（） 判断目前状态

5、（f，w，s，v）是否安全的函数is_safe（） 判断顶点i和顶点j之间是否可转换的函数is_connected（） 深度优先搜索从u到v的简单路径的函数dfs_path 输出从u到v的简单路径，即顶点序列中不重复出现的路径print_path（）各函数关系如下：maincreateglocateis_safeis_connecteddfs_pathprint_pathis_safeis_connected图1 各函数关系图3、 详细设计和编码实现概要设计中定义的所有数据类型，对每个操作作出伪码算法。数据结构#define maxnumvertices 10 /最大顶点数typedef st

6、ruct /图的顶点类型 int farmer,wolf,sheep,veget;vextype;typedef struct int vertexnum,currentedges; /图的当前顶点数和边数 vextype verticeslistmaxnumvertices; /顶点向量（代表顶点） int edgemaxnumverticesmaxnumvertices;/邻接矩阵 /用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关adjgraph;图的基本操作1.查找顶点（f，w，s，v）在图中的位置int locate(adjgraph *g,int f,int w,int

7、s,int v) int i; for(i=0;ivertexnum;i+) if(g-verticeslisti.farmer=f & g-verticeslisti.wolf=w & g-verticeslisti.sheep=s & g-verticeslisti.veget=v) return(i); /返回当前位置 return (-1); /没有找到此顶点2.判断目前的（f，w，s，v）是否安全当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的，否则安全int is_safe(int f,int w,int s,int v) if(f!=s & (w=s|s=v) return

8、 (0);/不安全返回0 else return (1); /安全返回13. 判断状态i与状态j之间是否可转换显然每次转换农夫都在移动，而农夫移动时最多只能携带一个物件，故每次状态转换，其他3件只能有一件移动或都不移动，能转换时返回1，不能转换时返回0，代码如下：int is_connected(adjgraph *g,int i,int j) int k=0; if(g-verticeslisti.wolf!=g-verticeslistj.wolf) k+; if(g-verticeslisti.sheep!=g-verticeslistj.sheep) k+; if(g-vertices

9、listi.veget!=g-verticeslistj.veget) k+; if(g-verticeslisti.farmer!=g-verticeslistj.farmer & kedgeij=g-edgeji=1;即初始化邻接矩阵。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+)/因为只有0和1俩个状态故循环都时从0开始1结束 for(s=0;s=1;s+) for(v=0;vverticeslisti.farmer=f; g-verticeslisti

10、.wolf=w; g-verticeslisti.sheep=s; g-verticeslisti.veget=v; i+;/统计安全顶点个数 g-vertexnum=i; for(i=0;ivertexnum;i+) /邻接矩阵初始化即建立邻接矩阵 for(j=0;jvertexnum;j+) if(is_connected(g,i,j) /状态i与状态j之间可转化，初始化为1，否则为0 g-edgeij=g-edgeji=1; else g-edgeij=g-edgeji=0; return;5.深度优先搜索u到v的简单路径深度优先: 每个时刻探索一条路径，并记录访问过的合法状态，一直向前

11、探视，直到走不通时回溯。显然，应该用堆栈来保存访问过的状态，以便回溯。具体分析如下：首先访问u，并标记；访问下一个与u可转换的顶点v1，并标记，将v1存储起来；再从v1开始，选取下一个可以与v1转换的顶点v2访问，标记，并存储；重复直到某顶点vi没有可以转换的顶点，此时退后一步查找vi-1可有可以转换的顶点；以上任何时刻访问到了v即停止，直至到v。详细代码如下：void dfs_path(adjgraph *g,int u,int v) int j; visitedu=true; /标记已访问过的顶点 for(j=0;jvertexnum;j+) if(g-edgeuj & !visitedj

12、 & !visitedv) /u，j可转换，且j，v都未被访问过 pathu=j;/将顶点j保存 dfs_path(g,j,v); 6.输出u到v的简单路径路径的保存是用前一个顶点u的序号作为数组path的下标即pathu保存下一个顶点j的，故在输出时，先将k=u，然后输出u的状态，再将k=pathk，输出当前顶点状态，以此循环直到k=v，最后输出v的状态。void print_path(adjgraph *g,int u,int v)/输出从u到v的简单路径，即顶点序列中不重复出现的路径 int k; k=u; while(k!=v) cout(verticeslistk.farmer,ve

13、rticeslistk.wolf,verticeslistk.sheep,verticeslistk.veget);coutendl;k=pathk; cout(verticeslistk.farmer,verticeslistk.wolf ,verticeslistk.sheep,verticeslistk.veget); coutendl;7.主函数void main() cout0表示本岸，1表示对岸n;cout(农夫，狼，羊，蔬菜)n;int i,j; adjgraph graph; createg(& graph); for(i=0;igraph.vertexnum;i+) visi

14、tedi=false; /置初值 i=locate(&graph,0,0,0,0);/找到最初状态的顶点位置 j=locate(&graph,1,1,1,1);/全部过河后的状态的顶点位置 dfs_path(&graph,i,j);/深度优先搜索从开始状态到全部过河的一条安全路径 if(visitedj)/若搜索到了一条安全路径则打印出安全路径 print_path(&graph,i,j);return;4、 上机调试经分析可知，该问题总共有2种路径可行，分别是：带羊到对岸 ，空手回本岸 ，带狼到对岸 ，带羊回本岸 ，带菜到对岸 ，空手回本岸 ，带羊到对岸；带羊到对岸，空手回本岸，带菜到对岸

15、，带羊回本岸 ，带狼到对岸 ，空手回本岸 ，带羊到对岸。本程序输出的路径是前一种方案，具体见测试结果截图部分。本来想要2种方案都输出的，但是还没能如愿解决。另外本程序在搜索路径是采用的是dfs即深度优先搜索，还可用bfs即广度优先搜索。深度优先: 每个时刻探索一条路径，并记录访问过的合法状态，一直向前探视，直到走不通时回溯。显然，应该用堆栈来保存访问过的状态，以便回溯。广度优先：在所有可能的路径上齐头并进，同时探索可能性。这样，在某个位置会有多个分支，他们都要进行处理，因此需要一个缓冲队列，把他们进对保存，在依次出对处理。这样才能应付所有的状态。在创建安全图时需要创建邻接矩阵来存储图，时间复杂

16、度为o（n2），n为顶点数，在深度优先搜索安全路径时，时间复杂度为o（n+e），e为边数，其他相关的操作的算法的时间复杂度均要比前二者小，故本程序的时间复杂度为t（n）= o（n2）。5、用户使用说明在vc+6.0下运行程序即可得到解决问题的方案，不需要其他操作6、 测试结果图2测试结果图7、参考文献1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。2 胡学纲. 数据结构与算法设计指导. 北京：清华大学出版社，1999. 8、 附录#include#define maxnumvertices 10 /最大顶点数typedef enum false,true boole

17、an;typedef struct /图的顶点类型 int farmer,wolf,sheep,veget;vextype;typedef struct int vertexnum,currentedges; /图的当前顶点数和边数 vextype verticeslistmaxnumvertices; /顶点向量（代表顶点） int edgemaxnumverticesmaxnumvertices;/邻接矩阵 /用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关adjgraph; /定义图的邻接矩阵存储结构boolean visitedmaxnumvertices; /对已访问的顶点

18、进行标记（图的遍历）int pathmaxnumvertices;/保存dfs搜索到的路径，即与某顶点到下一顶点的路径int locate(adjgraph *g,int f,int w,int s,int v)/查找顶点（f，w，s，v）在顶点向量中的位置 int i; for(i=0;ivertexnum;i+) if(g-verticeslisti.farmer=f & g-verticeslisti.wolf=w & g-verticeslisti.sheep=s & g-verticeslisti.veget=v) return(i); /返回当前位置 return (-1); /没

19、有找到此顶点int is_safe(int f,int w,int s,int v)/判断目前的（f，w，s，v）是否安全 if(f!=s & (w=s|s=v) return (0); /当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的 else /否则安全 return (1); /安全返回1int is_connected(adjgraph *g,int i,int j)/判断状态i与状态j之间是否可转换 int k=0; if(g-verticeslisti.wolf!=g-verticeslistj.wolf) k+; if(g-verticeslisti.sheep!=g-v

20、erticeslistj.sheep) k+; if(g-verticeslisti.veget!=g-verticeslistj.veget) k+; if(g-verticeslisti.farmer!=g-verticeslistj.farmer & k=1) /以上三个条件不同时满足两个且农夫状态改变时，返回真 /也即农夫每次只能带一件东西过桥 return(1); else return(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(

21、s=0;s=1;s+) for(v=0;vverticeslisti.farmer=f; g-verticeslisti.wolf=w; g-verticeslisti.sheep=s; g-verticeslisti.veget=v; i+; g-vertexnum=i; for(i=0;ivertexnum;i+) /邻接矩阵初始化即建立邻接矩阵 for(j=0;jvertexnum;j+) if(is_connected(g,i,j) g-edgeij=g-edgeji=1; /状态i与状态j之间可转化，初始化为1，否则为0 else g-edgeij=g-edgeji=0; return;void print_path(adjgr