实验报告 测试.docx

《实验报告 测试.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、【摘要】中国邮政问题是算法中的金典问题。该问题是哈密尔顿回路问题的变种，同时该问题在很多问题中有所体现。本报告将描述如何利用哈密尔顿回路完成中国邮政问题，然后分析该算法需要的时间代价和空间代价。【关键词】中国邮政问题、哈密尔顿回路目录1.设计内容和要求21.1设计内容21.2设计要求22.问题分析22.1中国邮路问题22.2解决问题的方案23.概要设计23.1建立相关数据模型23.2主要函数算法描述23.3相关算法性能分析24.详细设计及代码实现24.1代码实现25.系统实现25.1系统操作25.2测试数据26.总结21.设计要求和内容41.1设计内容41.2设计要求5设计要求和内

2、容1.1设计内容邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每房屋只一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。编程要求：层次一：只求解用户输入的图形的中国邮路问题要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最终结果。层次二：加入图形编辑器系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形和最终结果。层次三：附加要求能够图形显示求解过程。设计要求问题分析2.1中国邮路问题思路:对一个指定的无向图如下图型,要求一个邮递员经过每个不重

3、复的房屋,每个房屋只能走一遍.送到他所管辖的客户中，再返回邮局,要求走过的路径最短.从规则中可以很容易的发现:路径回路是由这张无向图的哈密顿回路的结果.同时在这几个回路中找出权最短路径.只要通过哈密顿最短路径回路就可以解决相应问题.2.2解决问题的方案解决该问题的程序需要提供一下输入输出输入参数：输入数据有多组数据组成。每组数据仅有一行，不超过100个字符，表示一个无向图顶点和顶点的距离。输出参数：对于输入的数据，进行运算找出最短的回路。例如图1输入的顶点数和边数分别为3和3顶点序号-权值-顶点序号为：011012122输出：最短哈密尔顿回路为6路径为0-1-22.3设计思路该问题

4、的解决必须能够建立一棵状态空间是一棵完全树，在求解过程中求所访问的节点数。因此必须使用哈密尔顿回路算法来完成相关操作。所谓哈密尔顿回路是指在一个无向图中，有一条回路起点和终点一样且每一个顶点在该回路中出现且仅出现一次。该问题需要解决两个主要问题，找出回路和最短路径。设计编制两个函数。函数功能注意条件及限制规则search(p)哈密尔顿回路寻找函数当顶点未被遍历且与刚遍历的顶点之间有边，则退出当下循环；当顶点号大于N，则对回路数统计，输出；如果不满足前一个条件，则退回前一个顶点进行重新遍历。shaixuan()对遍寻的结果进行筛选对回路求路径长；存储路径长；对路经长比较3.概要设计3

5、.1建立相关数据模型哈密尔顿回路寻找函数对遍寻的结果进行筛选，判断是否有哈密尔顿回路4.详细设计及代码实现4.1代码实现/********************此程序是用来进行中国邮路问题*******************//**********************欢迎使用*************************************/#include#include#include#include#defineMax100#defineINF6666usingnamespaces

6、td;/********************邻接矩阵的结构体的定义******************/typedefstructnode{intcost[Max][Max];//用来标记俩个顶点之间的权值intedges[Max][Max];//用来标记俩个顶点之间是否有边}list,*MG;intn=100;inta[2000][2000];//用来存储每次寻找到的哈密尔顿回路/***********************无向图初始化函数*******************/MGchushihua(){ints,i,j,e;intweight;MGp;p=(MG)mal

7、loc(sizeof(list));for(i=0;icost[i][j]=INF;//初始点的所有路径中各点到其他点的距离为无穷大p->edges[i][j]=0;//初始化每2个顶点之间没有边}printf("请输入无向图的顶点数n，和其边数e,格式：ne");scanf("%d%d",&n,&e);printf("请输入边与边之间的关系，格式：顶点序号-权值-顶点序号");//初始