实验6农夫、狼、羊和菜问题.docx

实验6：农夫、狼、羊和菜问题 一、 实验目的： 会定义图的抽象数据类型； 熟悉图的基本结构，掌握程序中的用户头文件、实现文件和主文件Z间的相 互关系及各自的作用； 熟悉对图的-?些基木操作和具体的函数定义； 掌握在实际问题屮运用所学知识解决实际问题的方法和步骤。 二、 实验内容描述： 有一农夫带着一条狼、一只羊和一筐菜，想从河的左岸乘船到右岸。但由于船太 小，农夫每次只能带一样东西过河，而且，如果没有农夫看管，则狼会吃羊，羊 会吃菜。问农夫怎样过河才能把每样东西安全地送过河。 三、 实验要求： 将上述问题用图表示出来； 选择图的一种存储结构，编写一个自动生成该图的算法； 3?在上述基础上编写求解该问题的算法程序，并用此程序上机运行、调试， 4.屏幕显示结果，能结合程序进行分析。 四、 问题分析： 该问题从表面上看，并不是一个图的问题，但可以把它用图表示出来，从而 转换为一个图的问题。在这个问题的解决过程中，农夫需要多次架船往返于两岸 Z间，每次可以带一?样东西或者自己单独过河，每一次过河都会使农夫、狼、羊 和菜所处的位置发生变化。如果用一个四元组(Fanner, Wolf, Sheep, Veget)表 示当前农夫、狼、羊和菜所处的位置，其中每个元素可以是0或1, 0表示在左 岸，1表示在右岸。这样，对这四个元素的不同取值可以构成16种不同的状态, 初始时的状态则为(0, 0, 0, 0),最终要达到的廿标为(1, 1, 1, 1)。状态之 间的转换可以有下面四种情况： 农夫不带任何东西过河，可表示为： (Farmer, Wolf, Sheep, Vegct) aFELnRcr, Wolf, Sheep, Vegct) 当农夫和狼在和同位置时，表示农夫带狼过河，即当Farmer=Wolf时： (Farmer, Wolf, Sheep, Veget) ([Farmer, !Wolf, Sheep, Veget) 当农夫和羊在相同位置时，表示农夫带羊过河，即当Farmer=Sheep时： (Farmer, Wolf, Sheep, Veget) (!Feinncr, Wolf, ! Sheep, Vcgct) 当农夫和菜在相同位置时，表示农夫带菜过河，即当Farmer=Veget时： (Farmer, Wolf, Sheep, Veget) ([Farmer, Wolf, Sheep, !Veget) 在这16种状态中，冇些状态是不安全的，是不允许出现的，如(1, 1, 0, 0) 表示农夫和狼在右岸，而羊和菜在左岸，这样羊会吃掉菜。如果从16种状态中 删去这些不安全状态，将剩余的安全状态之间根据上面的转换关系连接起来，就 得到如下图所示的图。 图1 图1农夫、狼、羊和菜问题的状态图 这样，原始问题就转换为在这个图中寻找一条从顶点(0, 0, 0, 0)到顶点(1, 1, 1, 1)的路径的问题。 五、存储结构： 采用邻接矩阵和邻接表都可以完成求图屮两顶点间的路径问题，这里，我们不妨 采用邻接矩阵存储结构。其中图的每个顶点结点包括四个域，类型定义为： typedef struct /*定义图的顶点类型*/ { int Farmer, Wolf, Sheep, Veget; }VexType; 图的邻接矩阵存储结构定义为： /*最大顶点个数*/ /*最大顶点个数*/ typedef struct int vexnum, c;VexType vex[VEX-NUM]; int vexnum, c; VexType vex[VEX-NUM]; int adj[VEX-NUM][VEX-NUM]; /*图的当前顶点数和边数*/ /*顶点向量*/ /*邻接矩阵*/ }AdjGraph; 六、 算法思想： 在这个问题屮，首先需要自动生成图的邻接矩阵存储，具体方法是先生成各种安 全状态结点，存放在顶点向量屮；再根据状态Z间的转换关系形成顶点Z间的所 有边，保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用深度优先搜 索思想求出从顶点(o, o, 0, 0)到顶点(1, 1, 1, 1)的一条简单路径。 七、 实验程序： #includestdio.h ^define VEX NUM 10 typedef enum{FALSE, TRUE}Boolean; typedef struct { int Farmer, Wolf, Sheep, Veget; }VexType; typedef struct { int vexnum, e; VexType vexs[VEX_NUM]; int adj[VEX_NUM][VEX_NUM]; }AdjGraph; Boolean visited[VEX_NUM]; int path[VEX NU