农夫过河问题

1、课程设计题目：农夫过河一.问题描述一个农夫带着一只狼、一只羊和一箜白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。过河有以下规则：(1)农夫一次最多能带一样东西(或者是狼、或者是羊、或者是白菜)过河；(2)当农夫不在场是狼会吃羊；(3)当农夫不在场是羊会吃掉白菜。现在要求为农夫想一个方案，能将3样东西顺利地带过河。从出事状态开始,农夫将羊带过河，然后农夫将羊待会来也是符合规则的，然后农夫将羊带过河仍然是符合规则的，但是如此这般往返，搜索过程便进入了死循环，因此，在这里，采用改进的搜索算法进行搜索。二.基本要求(1)为农夫过河问题

2、抽象数据类型，体会数据模型在问题求解中的重要性；(2)要求利用数据结构的方法以及C+的编程思想来完成问题的综合设计；(3)在问题的设计中，使用深度优先遍历搜索方式，避免死循环状态；(4)设计一个算法求解农夫过河问题，并输出过河方案；(5)分析算法的时间复杂度。三.概要设计(1)数据结构的设计typedefstruct/图的顶点(intfarmer;/农夫intwolf;/狼intsheep;/羊intveget;白菜Vertex;设计Vertex结构体的目的是为了存储农夫、狼、羊、白菜的信息，因为在遍历图的时候，他们的位置信息会发生变化，例如1111说明他们都在河的北岸，而0000说明他们都在

3、河的南岸。typedefstruct(intvertexNum;/图的当前顶点数VertexvertexVertexNum;/顶点向量(代表顶点)boolEdgeVertexNumVertexNum;/邻接矩阵.用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关AdjGraph;/定义图的邻接矩阵存储结构存储图的方法是用邻接矩阵，所以设计一个简单的AdjGraph结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。(2)算法的设计深度优先遍历基本设计思想：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的1/12边(x,y)。若发现顶点y已

4、访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。程序中的深度优先遍历算法如下：voiddfsPath(AdjGraph*graph

5、,intstart,intend)/深度优先搜索从u至1Jv的简单路径DFS-DepthFirstSearch(inti=0;visitedstart=true;/标记已访问过的顶点if(start=end)return;)for(i=0;i<graph->vertexNum;i+)(if(graph->Edgestarti&&!visitedi)(retPathstart=i;dfsPath(graph,i,end);)(3)抽象数据类型设计intlocate(AdjGraph*graph,intfarmer,intwolf,intsheep,intvege

6、t)/查找顶点(F,W,S,V)在顶点向量中的位置boolisSafe(intfarmer,intwolf,intsheep,intveget)/判断目前的(F,W,S,V)是否安全boolisConnect(AdjGraph*graph,inti,intj)/判断状态i与状态j之间是否可转换voidprintPath(AdjGraph*graph,intstart,intend)/输出从u至1Jv的简单路径，即顶点序列中不重复出现的路径voiddfsPath(AdjGraph*graph,intstart,intend)/深度优先搜索从u至1Jv的简单路径/DFS-DepthFirstSea

7、rch四.详细设计1 .问题遵循的原则(1)图：顶点和连线的集合，G=(V,E),其中V是图中顶点的有穷非空集合，E是两个顶点的关系的集合，即图中连线的集合。若E中顶点对<v,u>是有序的，则为有向图，否则为无向图。(2)网:带权值的图称为网(3)邻接矩阵：表示顶点之间连接关系的矩阵。2 .算法描述(1)深度优先遍历的递归算法：typedefenumFALSE,TRUEBoolean;/FALSE为0,TRUE为BooleanvisitedMaxVertexNum;访问标志向量是全局量voidDFSTraverse(ALGraph*G)/深度优先遍历以邻接表表示的图G,而以邻接矩阵

8、表示G时，算法完全与此相同inti;for(i=0;i<G->n;i+)visitedi=FALSE;/标志向量初始for(i=0;i<G->n；i+)if(!visitedi)/vi未访问过DFS(G,i);以vi为源点开始DFS搜索/DFSTraverse(2)邻接矩阵表示的深度优先遍历算法：voidDFSM(MGraph*G,inti)以vi为出发点对邻接矩阵表示的图G进彳TDFS搜索，设邻接矩阵是0,l矩阵intj;printf("visitvertex:%c",G->vexsi);访问顶点vivisitedi=TRUE;for(j=0

9、;j<G->n;j+)/依次搜索vi的邻接点if(G->edgesij=1&&!visitedj)DFSM(G,j)/(vi,vj)CE,且vj未访问过，故vj为新出发点/DFS五.运行与测试1 .程序清单#include<iostream>usingnamespacestd;#defineVertexNum100/最大顶点数typedefstruct/图的顶点intfarmer;/农夫intwolf;/狼intsheep;/羊intveget;白菜Vertex;typedefstructintvertexNum;/图的当前顶点数Vertexver

10、texVertexNum;/顶点向量(代表顶点)boolEdgeVertexNumVertexNum;/邻接矩阵.用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关AdjGraph;/定义图的邻接矩阵存储结构boolvisitedVertexNum=false;/对已访问的顶点进行标记(图的遍历)intretPathVertexNum=-1;/保存DFS搜索到的路径，即与某顶点到下一顶点的路径/查找顶点(F,W,S,V)在顶点向量中的位置intlocate(AdjGraph*graph,intfarmer,intwolf,intsheep,intveget)/从0开始查找for(int

11、i=0;i<graph->vertexNum;i+)(if(graph->vertexi.farmer=farmer&&graph->vertexi.wolf=wolf&&graph->vertexi.sheep=sheep&&graph->vertexi.veget=veget)(returni;返回当前位置)return-1;/没有找到此顶点)/判断目前的(F,W,S,V)是否安全boolisSafe(intfarmer,intwolf,intsheep,intveget)(当农夫与羊不在一起时，狼与羊或羊

12、与白菜在一起是不安全的if(farmer!=sheep&&(wolf=sheep|sheep=veget)(returnfalse;)else(returntrue;/安全返回true)/判断状态i与状态j之间是否可转换boolisConnect(AdjGraph*graph,inti,intj)(intk=0;if(graph->vertexi.wolf!=graph->vertexj.wolf)(k+;if(graph->vertexi.sheep!=graph->vertexj.sheep)(k+;if(graph->vertexi.vege

13、t!=graph->vertexj.veget)(k+;/以上三个条件不同时满足两个且农夫状态改变时，返回真，也即农夫每次只能带一件东西过桥if(graph->vertexi.farmer!=graph->vertexj.farmer&&k<=1)(returntrue;else(returnfalse;)/创建连接图voidCreateG(AdjGraph*graph)(inti=0;intj=0;/生成所有安全的图的顶点for(intfarmer=0;farmer<=1;farmer+)(for(intwolf=0;wolf<=1;wol

14、f+)(for(intsheep=0;sheep<=1;sheep+)(for(intveget=0;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->vertexN

15、um;i+)(for(j=0;j<graph->vertexNum;j+)(/状态i与状态j之间可转化，初始化为1,否则为0if(isConnect(graph,i,j)(graph->Edgeij=graph->Edgeji=true;)else(graph->Edgeij=graph->Edgeji=false;)return;)/判断在河的那一边char*judgement(intstate)if(state=0)return("南岸");elsereturn("北岸");/return(0=state)?&qu

16、ot;南岸"："北岸");)/输出从u到v的简单路径，即顶点序列中不重复出现的路径voidprintPath(AdjGraph*graph,intstart,intend)(inti=start;cout<<"farmer"<<",wolf"<<",sheep"<<",veget"<<endl;while(i!=end)(cout<<"("<<judgement(graph->

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

18、h->vertexi.farmer)<<","<<judgement(graph->vertexi.wolf)10<<","<<judgement(graph->vertexi.sheep)<<","<<judgement(graph->vertexi.veget)cout<<endl;/深度优先搜索从u到v的简单路径/DFS-DepthFirstSearchvoiddfsPath(AdjGraph*graph,intstart,intend)inti=0;visitedstart=true;/标记已访问过的顶点if(start=end)return;for(i=0;i<graph->vertexNum;i