三件有制约关系物品过河问题

《数据结构项目实践》集中上机

1．实验题目

三件有制约关系物品过河问题（90分）

有一人要将自己的兔子、蔬菜和狐狸等三件物品运过河。但过河所用的船每次只能装其中的两件，而这三件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模型，并编程实现这一问题的求解。

2．数据输入和输出

输出时我尽力使界面做的漂亮，使问题求解的最终结果显而易见。由于我们考虑到问题的具体实现，所以将运行出的结果（矩阵形式）特地转化成文字语言并且输出。

3.数据结构及其存储结构

(1)选择对应的数据结构，由于问题的实现是寻找一条路径，那么主要的数据结构就应该是图或者是树，对这个问题我选择图。

(2)选择存储结构，由于问题的规模很小，且总的状态种类很少，所以，我选择邻接矩阵作为图的存储结构。

4.算法的基本思想

算法的思想其实很简单，首先在创立节点时利用is_safe()函数就将不安全的结点全部排除，再利用is_connected（）函数 就可将每个结点的后继结点得到。之后利用深度优先搜索就可以找到实现这一问题的路径。 问题的分析

①每一个物体都只有两个状态，在原岸或者在对岸

②从整体上看又有很多种不同的状态(如农夫和羊在对岸,狼和白菜在原岸) ③从一个状态可合法地转到另外几个状态(如农夫自己过河或农夫带着羊过河) ; ④有些状态不安全(如农夫在对岸,其他东西在原岸) ;

⑤有一个初始状态(都在原岸)，有一个结束状态集(都在对岸)。 问题模型的建立

问题的模型建立：为了方便解决问题，又结合实际问题的特征，我们可以将这个问题模型化。首先，采用二进制中的0/1表示每一个物体的两种状态，用一个四位的二进制数表示一种整体的状态，这样就使原来的问题变的更加易于理解，有利于我们找到合适的数据结构类型来实现问题。

根据对象的状态分为过河（1）和不过河（0），此对象集合就构成了一个状态空间。问题就是在这个状态空间内搜索一条从开始状态到结束状态的安全路径。显然，其初始状态为四个对象都不过河（都为0），结束状态为四对象全部过河（都是1）。状态到下一状态可以通过合法的途径获得，即搜索条件明确。 这其中可以根据相互之间的制约关系，排除不合法的状态。通过分析得到的各种状态间的关系转换图如下图

系统状态转换关系图

其中双向的箭头表示状态可逆,即农夫可以带着某种东西过去,也可以带着该东西回来。箭头上的字母表示农夫所携带的东西:Fa (Farmer) ,Fo(Fox) ,R(Rabbit),V(Vegetable)分别表示农夫自己、农夫携带狐狸、农夫携带兔子、农夫携带菜过河。 5.调试通过的源程序 #include

#define VEX_NUM 10 //最大顶点数 typedef enum { FALSE,TRUE} Boolean; typedef struct {

int Farmer,Fox,Rabbit,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_NUM],y[VEX_NUM];

int locate(AdjGraph *G,int Fa,int Fo,int R,int V) //查找顶点（Farmer，Fox，Rabbit，Vegetable）在顶点向量中的位置 { int i;

for(i=0;ivexnum;i++)

if(G->vexs[i].Farmer==Fa&&G->vexs[i].Fox==Fo&&G->vexs[i].Rabbit==R&&G->vexs[i].Veget==V) return(i); return(-1); }

int is_safe(int Fa,int Fo,int R,int V) {

if(Fa!=R&&(Fo==R||R==V))//fa!=r? return(0); else return(1); }

int is_connected(AdjGraph *G,int i,int j) { int k; y[0]=0; k=0;

if(G->vexs[i].Fox!=G->vexs[j].Fox)

k++;

if(G->vexs[i].Rabbit!=G->vexs[j].Rabbit) k++;

if(G->vexs[i].Veget!=G->vexs[j].Veget) k++;

if(G->vexs[i].Farmer!=G->vexs[j].Farmer&&k<=1) return(1); else return(0); }

void CreatG(AdjGraph *G) {

int i,j, Fa,Fo,R,V; i=0;

for(Fa=0;Fa<=1;Fa++)//形成所有安全的状态结点 for(Fo=0;Fo<=1;Fo++) for(R=0;R<=1;R++) for(V=0;V<=1;V++) if(is_safe(Fa,Fo,R,V)){ G->vexs[i].Farmer=Fa; G->vexs[i].Fox=Fo;

G->vexs[i].Rabbit=R; G->vexs[i].Veget=V; i++; }

G->vexnum=i;

for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) if(is_connected(G,i,j)) G->adj[i][j]=G->adj[j][i]=1;

else

G->adj[i][j]=G->adj[j][i]=0; return; }

void print_path(AdjGraph *G,int u,int v)//输出从u到v的简单路径 {

int k,i=1; k=u;

printf(\状态变化图\\n\

printf(\表示到达对岸，'0'表示在原岸)\\n\

printf(\农夫 狐狸 兔子 蔬菜\\t 农夫 狐狸 兔子 蔬菜\\n\while(k!=v){

printf(\※\\t( %d, %d , %d , %d ) ※

\if(!k)

printf(\均在原岸\\t ※\\n\else {

if(G->vexs[k].Farmer) printf(\在对岸\

else if(i>1&&G->vexs[y[i-1]].Farmer) printf(\回原岸\

else printf(\在原岸\if(G->vexs[k].Fox) printf(\在对岸\else printf(\在原岸\ if(G->vexs[k].Rabbit) printf(\在对岸\else printf(\在原岸\ if(G->vexs[k].Veget)

printf(\在对岸 ※\else printf(\在原岸 ※\printf(\}

printf(\※\\t ↓ ※\\t ↓ \\t\\t ※ \\n\k=path[k]; y[i++]=path[k]; }

printf(\※\\t( %d, %d , %d , %d )\\t ※

\ printf(\均到达对岸\\t ※\\n\}

void DFS_path(AdjGraph *G,int u,int v)//求从u到v的简单路径 { int j;

visited[u]=TRUE;

for(j=0;jvexnum;j++)

if(G->adj[u][j]&& !visited[j] && !visited[v]){ path[u]=j; DFS_path(G,j,v); } }

void main() { int i,j; AdjGraph graph; CreatG(&graph);

for(i=0;i

i=locate(&graph,0,0,0,0);

j=locate(&graph,1,1,1,1); DFS_path(&graph,i,j); if (visited[j])

print_path(&graph,i,j); return; }

6.运行结果

7.程序的优缺点

程序明确了该题目的基本要求，友好的界面让大家清晰的知道了农夫、狐狸、兔子、蔬菜的过河顺序。

但是，输出的路径只有一个，因为两条路径基本相同，所以为了程序的复杂程度，我们就只输出一条。

另为，虽然我们已经尽力使界面美观，形象的输出问题的解，但总还不是太形象。

8.程序的时空性能

由于程序的规模很小，所以涉及到的数据也很少，所以时间复杂度和空间复杂度实际上也应该很小。对于此程序中的具体算法，比如说，深度优先搜索，DFS_path(),由于采用的是邻接矩阵的存储方式，所以它找到每个顶点的所需时间是O(n2),其中n为顶点数。如果

此程序涉及到一个大宗的数据，O（n2）确实是比较大，但本问题只涉及到最多16个数据，所以对于这个程序而言，时间复杂度和空间复杂度都不是最为主要的问题。但我们还是要坚持利用时间复杂度和空间复杂度很小的算法，以体现编程中的。

9.改进思想

由于本程序解决的这个问题功能单一，所以拓展的空间有限。但我们仍然有扩张之处： 一、因为程序中输出的路径是一条，但实际上存在两条路径。但我们观察一下这两条路径.

第一条：（0000）→（1010）→（0010）→（1011）→（0001）→（1101）→（0101）→（1111）

第二条：（0000）→（1010）→（0010）→（1110）→（0100）→（1101）→（0101）→（1111）

这其中只有两个不同，只在于是先将Fox带过去，还是先将Veget带过去，只是时间顺序的问题，对于其他的方面没有任何影响。所以这个对于题目中的问题似乎没有扩展之处，但延伸到其他问题，可能会出现路径长度不同等问题，这样对于用户可能就希望得到代价最短的那条路径。这时，我们打算将每条路径输出，然后供用户选择其中最理想的一条。考虑到算法，我们可以利用邻接表作为图的存储方式，然后从起始位置开始，深度优先搜索，搜索到最终位置是，输出这条路径，然后从起始位置的另为一个后继开始，进行深度优先搜索，然后循环，直到输出所有路径。

二、考虑到实际情况，每一条路径对农夫可能要付出不同的劳动力。比如说，农夫可能希望多带几次Veget过去，也不愿带一次Fox过去。而就此题而言，这种情况也不会发生，在观察一下他的两条路径：

第一条： 第二条： 带兔子过河 带兔子过河

乘船自己回原岸 乘船自己回原岸

带蔬菜过河 带狐狸过河

带兔子回原岸 带兔子回原岸

带狐狸过河 带蔬菜过河

自己回原岸 自己回原岸

带兔子过河 带兔子过河

很明显，这只是狐狸，蔬菜过河的时间顺序交换，与最终结果，对农夫来说的劳动力没有任何影响。

但如果真的存在劳动力不同的路径，我们的算法就会做出相应的改变。和这道题不同的是，从一种状态转移到另一种我们都要赋予一定的权值，这样从初始状态到最终状态就有一个表示劳动力付出的值，我们也将用网（边上带权值的图）这种数据结构，同样使用邻接表的存储结构，这样就可以求出每一条路径的同时，一同得到路径长度。这样可以使用户选择路径长度最短的那条。

另外，我们可以选择用Dijkstra（迪杰斯特拉）算法求最短路径，这样就可以方便用户找到最轻松实现自己的目的的路径。

三．对于四件有制约关系的物品过河问题，相对于三件更加复杂，但解决问题的思路大致相同。只是细节上更加复杂. 10.心得体会

数据结构是计算机学科的一门综合性的专业基础课，也是计算机学科的核心课程，在整个学科知识体系中占据非常重要的地位。通过该课程的学习，不仅为后续课程打好理论基础，而且进一步提高数据抽象能力和程序设计能力。数据结构课程内容多、概念多、方法多、高度抽象、逻辑性强、技巧性强、实践性强。

而最为有效的方法就是实践。的确，每一次从这样为期一个星期的集中上机，我们都收获颇丰。

一方面就是对数据结构的一些概念，数据结构和算法的思想理解的更加深刻，另一方面，也极大的锻炼了我们的实际动手操作能力。这对于工科要求我们要有极强的动手能力是完全吻合的。

通过这次集中上机，更加认识到数据结构的重要性，他的确是语言更加容易表达出来。比如说，栈这种数据结构，先进后出的线性表。假如我们对此不了解，那解决一些问题就会是

工程量很大，浪费很多时间，但效果可能还不是十分理想，但栈就为我们解决一大类问题提供了捷径。比如说，括号匹配问题啊，八皇后问题啊，都很能体现数据结构，栈的独特之处，优先之处。

当然，对于我们刚刚学习数据结构一个学期的新手，对一个问题立即找到最佳的数据结构类型来实现它显然存在一定的困难，但通过自己仔细的分析，加上一些信息的参考，我们最终还是完成了我们的选的任务。虽然我们的程序中也许不够完美，但通过一星期的努力，我们还算圆满完成了我们的任务，这总会有一种成就感，也总能激起我们的热情。

但通过这个，我们还有了更大的收获，就是要考虑另一个方面的问题，用户，公司。有时，你的程序要切实的考虑到用户群，可能用户没有计算机基础。所以，程序首要考虑的要加入用户。当然，公司有时要求我们要有十分漂亮的界面，可能有时我们只考虑到整个程序的功能是否完善，而忽略了用户期望的。这也是人性化的一方面，更是我们值得思考和改进的地方。

总之，做什么事情都要对认真，既然是该你做的事，肯定是你应该有这个能力，即使能力不够，也是应该借这个机会来培养。所以放心大胆地做，对自己有信心，就有动力。有人说，世上的事就怕认真二字。确实，做什么，只是认真地去做，踏踏实实，戒躁戒躁，静静地思考，慢慢地进步，真的是天下无难事。这就是我这次课程设计中得到的最大的体会，受益匪浅。

本文来源：https://www.bwwdw.com/article/ggvo.html