农夫过河问题的算法与实现

1、 农夫过河问题的算法与实现院（系）名称 专 业 班 级 学 号 学 生 姓 名 指 导 教 师 年 月 日 目录引言.11. 问题的描述.22. 需求分析.33. 概要设计.4 3.1数据结构的设计.4 3.2算法的设计.5 3.3抽象数据类型的设计.54. 详细设计.6 4.1算法的主要思想.6 4.2主要功能函数设计.7 4.3算法的实现.75. 代码实现.106. 测试与运行.18 6.1测试工具.18 6.2运行结果.18 七.总结与体会.19八.参考文献.20 农夫过河问题的算法与实现 引言所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到北岸。一条小船只能容

2、下他和一件物品, 只有农夫能撑船。问农夫怎么能安全过河, 当然狼吃羊, 羊吃白菜, 农夫不能将这两种或三种物品单独放在河的一侧, 因为没有农夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径.一.问题的描述任何的实际问题，都可以抽象成固定的数学模型，然后再根据模型解决问题。这样就可以不考虑繁琐的实际过程，从而简化问题。在我们的问题中，过河与没过河是两种不同的状态。农夫、狼、羊和菜，分别处于这两种状态。而，如果把他们看成一个系统，则农夫、狼、羊和菜的不同状态组合成系统的2的4次方种，即16种状态。但在

3、系统的16种状态中，有些不满足题给条件，应给予剔除。剔除的判断条件：羊跟狼、菜状态相同，且不同于农夫的状态。当我们挑选好一系列系统的合法状态后，我们的问题就清晰了很多。我们不妨设，没过河状态为0，过河为1。我们的问题就抽象为，系统从初始状态（0000），经过有限的合法状态，到达最终状态（1111）的过程。系统不同的合法状态之间，可能，有的有路，有的则不能到达。具体的判断条件是，农夫可以与一件物品同时边，或自己单独变。根据这一个条件，我们可以抽象出一个图来：系统的每一种状态视为一个节点，满足条件的节点间有一条路。这样问题就抽象为，在无向图中找一条路。二、需求分析1、针对实现整个过程需要多步，不同

4、步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。2、题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到。 3、题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。4、 输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述

5、内容，并使界面所示方案清晰简洁。 三.概要设计3.1数据结构的设计利用图论知识求解的过程。假设分别用farmer表示农夫，wolf表示狼，sheep表示羊，veget表示白菜。初始状态是f、w、s、v都在原岸，即初始状态V1为=f,w,s,v，在原岸全部可能出现的状态为以下16种：fwsv、fwv、fsv、wsv、fw、fs、fv、ws、wv、sv、f、w、s、v、，这里表示原岸是空集， 即人、狼、羊、白菜都已运到河的对岸去了。 根据题意可以得到，这16种情况中有6种情况是不允许出现的。它们是：wsv（狼、羊、白菜）、fw（农夫、狼）、fv（农夫、白菜）、ws（狼、羊）、 sv（羊、白菜）、f

6、（农夫）。如fv表示人和白菜在原岸，而狼和羊在对岸，这显然是不行的。因此，允许出现的情况只有10种。 我们构造一个图，它的顶点就是这10种状态。如果船某次从河的一岸划往另一岸时，使原岸的状态从V变成V，我们就作一条从V到V的弧，这样就可以得到如下图所示的有向图人狼羊白菜 人狼 人狼白菜 人羊白菜 人羊 狼白菜 狼 草 羊 空 由于船是在两岸间往返的，那么“过河”问题就转换成在上图中找出一条由结点fwsv到结点的路径，这条路径中相邻的两条弧或者都是由同一点引出的，或者都是进入同一个结点的，这样的路径是很容易找到的。从图中得到两条这样的路径，路径一：人狼羊白菜狼白菜人狼白菜白菜人羊白菜羊人羊，路径

7、二：人狼羊白菜狼白菜人狼白菜狼人狼羊羊人羊，它们的长度都是7，也就是说，农夫至少要经过7次摆渡才能将狼、羊、白菜都安全摆渡到对岸，可以有两种方案。如果要求解至少需要摆渡的次数，那就是去找路径长度最小的路径。从上面的分析得知，需要在图中找出一条从顶点fwsv到顶点的最短路径。采用广度优先搜索算法：用一个具有四个元素的数组来表示人、狼、羊、白菜在原岸的状态。初始顶点V1为人、狼、羊、白菜都在原岸，即V1=1，1，1，1，当人或某一件物品在对岸时，相应的数组元素值置为0。扩展新顶点所用的运算算符有以下四种情况：农夫独自摆渡过河，农夫带着狼摆渡过河，农夫带着羊摆渡过河，农夫带着白菜摆渡过河。约束条件为

8、当农夫与羊不在一起时，狼与羊或羊与白菜不能在一起，因为在无人看管的情况下，狼要吃羊，羊要吃白菜。按照这样的顶点产生规则和约束条件我们可以在程序中建立如上图所示的有向图，同时，遍历这个有向图，找出顶点到顶点的最短路径和路径长度。3.2算法的设计本程序可以分成四个模块，分别是：找到所有情况的点、从中挑选出满足题意的点、创建满足题意的点之间的边、通过图的深度优先遍历找到过河方案。各模块之间的关系图如下：找到所有情况的点（即0000-1111共16种组合）挑出符合题意的点（即农夫不在时，狼不和羊、羊不和菜在一起）找到符合题意点之间边的关系通过图的深度优先遍历找到过河方案3.3抽象数据类型的设计 本题采

9、用的是图，因此要用到定义图的结构体 typedef struct / 图的顶点 int farmer; / 农夫int wolf; / 狼int sheep; / 羊int veget; / 白菜Vertex; typedef struct int vertexNum; / 图的当前顶点数 Vertex vertexVertexNum; / 顶点向量（代表顶点） bool EdgeVertexNumVertexNum; / 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 AdjGraph; / 定义图的邻接矩阵存储结构 四.详细设计4.1算法的主要思想为简化结点，将农夫

10、、狼、羊、白菜用0和1两种状态量表示，0表示在河的南岸，也就是初始所在的河岸。1表示在河的北岸，即渡过河到达的对岸。那么初始状态即为0000，将其变为1111的中间状态量即为过河方案。那么就从16种所有情况的顶点中选择符合题意的结点，因为并不是所有点都满足题意，限制要求为农夫每次最多可带狼、羊、白菜中的一个过河，农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。选出所有满足题意的结点后，就要构造边，边即为符合题意两结点之间的连接。中间有边的两结点必须符合农夫的状态在变，并且农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。选出所有符合题意的结点和边后就构成了图，采用邻接表的存储结构

11、，然后通过图的深度优先遍历，将所有满足题意的结点遍历一遍并输出，到1111时即输出了过河方案的全部步骤。初始状态 00001001安全1010不安全1000不安全1100不安全0000重复0001安全1011安全1101安全1001安全0010安全0001重复0011不安全0100安全0001重复0101不安全0000重复0001重复1011重复1110安全1010不安全1101重复1110安全1100不安全1111过河成功0110安全0110安全4.2主要功能函数设计1.查找顶点在顶点向量中的位置int locate(AdjGraph *graph, int farmer, int wolf

12、, int sheep, int veget)2. 判断目前的（F，W，S，V）是否安全 bool isSafe(int farmer, int wolf, int sheep, int veget) 3.判断状态i与状态j之间是否可转换 bool isConnect(AdjGraph *graph, int i, int j)4.创建连接图void CreateG(AdjGraph *graph)5.输出从u到v的简单路径，即顶点序列中不重复出现的路径 void printPath(AdjGraph *graph, int start, int end) 6.深度优先搜索从u到v的简单路径

13、/DFS-Depth First Search void dfsPath(AdjGraph *graph, int start, int end)4.3算法的实现 查找顶点在顶点向量中的位置int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)for (int i = 0; i < graph->vertexNum; i+) if ( graph->vertexi.farmer = farmer && graph->vertexi.wolf = wolf &&

14、amp; graph->vertexi.sheep = sheep && graph->vertexi.veget = veget ) return i; /返回当前位置 return -1; /没有找到此顶点 判断目前的（F，W，S，V）是否安全 bool isSafe(int farmer, int wolf, int sheep, int veget) /当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的if ( farmer != sheep && (wolf = sheep | sheep = veget) ) return false

15、;else return true; / 安全返回true 判断状态i与状态j之间是否可转换 bool isConnect(AdjGraph *graph, int i, int j) int k = 0; if (graph->vertexi.wolf != graph->vertexj.wolf) if (graph->vertexi.wolf != graph->vertexj.wolf) k+; if (graph->vertexi.sheep != graph->vertexj.sheep) k+; if (graph->vertexi.ve

16、get != graph->vertexj.veget) k+; / 以上三个条件不同时满足两个且农夫状态改变时，返回真, 也即农夫每次只能带一件东西过桥 if (graph->vertexi.farmer != graph->vertexj.farmer && k <= 1) return true; else return false; 5. 代码实现#include<iostream>using namespace std;#define VertexNum 16 /最大顶点数 typedef struct / 图的顶点 int far

17、mer; / 农夫int wolf; / 狼int sheep; / 羊int veget; / 白菜Vertex; typedef struct int vertexNum; / 图的当前顶点数 Vertex vertexVertexNum; / 顶点向量（代表顶点） bool EdgeVertexNumVertexNum; / 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 AdjGraph; / 定义图的邻接矩阵存储结构 bool visitedVertexNum = false; / 对已访问的顶点进行标记（图的遍历） int retPathVertexNum

18、= -1; / 保存DFS搜索到的路径，即与某顶点到下一顶点的路径 int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)for (int i = 0; i < graph->vertexNum; i+) if ( graph->vertexi.farmer = farmer && graph->vertexi.wolf = wolf && graph->vertexi.sheep = sheep && graph->ver

19、texi.veget = veget ) return i; /返回当前位置 return -1; /没有找到此顶点 / 判断目前的（F，W，S，V）是否安全 bool isSafe(int farmer, int wolf, int sheep, int veget) /当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的if ( farmer != sheep && (wolf = sheep | sheep = veget) ) return false;else return true; / 安全返回true / 判断状态i与状态j之间是否可转换 bool isCon

20、nect(AdjGraph *graph, int i, int j) int k = 0; if (graph->vertexi.wolf != graph->vertexj.wolf) k+; if (graph->vertexi.sheep != graph->vertexj.sheep) k+;if (graph->vertexi.veget != graph->vertexj.veget) k+; / 以上三个条件不同时满足两个且农夫状态改变时，返回真, 也即农夫每次只能带一件东西过桥 if (graph->vertexi.farmer !=

21、 graph->vertexj.farmer && k <= 1) return true; else return false; / 创建连接图void CreateG(AdjGraph *graph) int i = 0;int j = 0; / 生成所有安全的图的顶点 for (int farmer = 0; farmer <= 1; farmer+) for (int wolf = 0; wolf <= 1; wolf+) for (int sheep = 0; sheep <= 1; sheep+) for (int veget = 0;

22、 veget <= 1; veget+) if (isSafe(farmer, wolf, sheep, veget) graph->vertexi.farmer = farmer; graph->vertexi.wolf = wolf; graph->vertexi.sheep = sheep; graph->vertexi.veget = veget; i+; / 邻接矩阵初始化即建立邻接矩阵 graph->vertexNum = i; for (i = 0; i < graph->vertexNum; i+) for (j = 0; j &

23、lt; graph->vertexNum; j+) / 状态i与状态j之间可转化，初始化为1，否则为0 if (isConnect(graph, i, j) graph->Edgeij = graph->Edgeji = true; else graph->Edgeij = graph->Edgeji = false; return; / 判断在河的哪一边char* judgement(int state)return ( (0 = state) ? "左岸" : "右岸" );/ 输出从u到v的简单路径，即顶点序列中不重复

24、出现的路径 void printPath(AdjGraph *graph, int start, int end) int i = start; cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;while (i != end) cout << "(" << judgement(graph->vertexi.farmer) <

25、< ", " << judgement(graph->vertexi.wolf)<< ", " << judgement(graph->vertexi.sheep) << ", " << judgement(graph->vertexi.veget) << ")" cout << endl;i = retPathi; cout << "(" << judgement

26、(graph->vertexi.farmer) << ", " << judgement(graph->vertexi.wolf)<< ", " << judgement(graph->vertexi.sheep) << ", " << judgement(graph->vertexi.veget) << ")"cout << endl; / 深度优先搜索从u到v的简单路径 /DFS-Depth First Search void dfsPath(AdjGraph *graph, int start, int end) int i = 0; visitedstart = true; /标记已访问过的顶点 if (start = end)return ;for (i = 0; i < graph->vertexNum; i+) if (graph->Edgestarti && !visitedi) retP