实验报告 测试.docx
【摘要】中国邮政问题是算法中的金典问题。该问题是哈密尔顿回路问题的变种，同时该问题在很多问题中有所体现。本报告将描述如何利用哈密尔顿回路完成中国邮政问题，然后分析该算法需要的时间代价和空间代价。【关键词】中国邮政问题、哈密尔顿回路 目录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设计要求和内容1.1 设计内容邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每房屋只一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。编程要求：层次一：只求解用户输入的图形的中国邮路问题 要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最终结果。层次二：加入图形编辑器 系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形和最终结果。层次三：附加要求 能够图形显示求解过程。设计要求问题分析2.1中国邮路问题思路:对一个指定的无向图如下图型,要求一个邮递员经过每个不重复的房屋,每个房屋只能走一遍.送到他所管辖的客户中，再返回邮局,要求走过的路径最短. 从规则中可以很容易的发现:路径回路是由这张无向图的哈密顿回路的结果.同时在这几个回路中找出权最短路径.只要通过哈密顿最短路径回路就可以解决相应问题.2.2 解决问题的方案解决该问题的程序需要提供一下输入输出输入参数：输入数据有多组数据组成。每组数据仅有一行，不超过100个字符，表示一个无向图顶点和顶点的距离。输出参数：对于输入的数据，进行运算找出最短的回路。例如图1 输入的顶点数和边数分别为3和3顶点序号-权值-顶点序号为：0 1 1 0 1 2 1 2 2 输出：最短哈密尔顿回路为6 路径为0-1-22.3 设计思路该问题的解决必须能够建立一棵状态空间是一棵完全树，在求解过程中求所访问的节点数。因此必须使用哈密尔顿回路算法来完成相关操作。所谓哈密尔顿回路是指在一个无向图中，有一条回路起点和终点一样且每一个顶点在该回路中出现且仅出现一次。该问题需要解决两个主要问题，找出回路和最短路径。设计编制两个函数。函数功能 注意条件及限制规则 search(p)哈密尔顿回路寻找函数当顶点未被遍历且与刚遍历的顶点之间有边，则退出当下循环；当顶点号大于N，则对回路数统计，输出；如果不满足前一个条件，则退回前一个顶点进行重新遍历。shaixuan()对遍寻的结果进行筛选对回路求路径长；存储路径长；对路经长比较3.概要设计3.1建立相关数据模型 哈密尔顿回路寻找函数对遍寻的结果进行筛选，判断是否有哈密尔顿回路4.详细设计及代码实现4.1代码实现/*此程序是用来进行中国邮路问题*/ /*欢迎使用*/ #include <stdio.h> #include <stdlib.h> #include <iostream>#include <windows.h>#define Max 100 #define INF 6666 using namespace std ;/*邻接矩阵的结构体的定义*/ typedef struct node int costMaxMax; /用来标记俩个顶点之间的权值 int edgesMaxMax; /用来标记俩个顶点之间是否有边list,*MG; int n=100; int a20002000; /用来存储每次寻找到的哈密尔顿回路/*无向图初始化函数*/ MG chushihua() int s,i,j,e; int weight; MG p; p=(MG)malloc(sizeof(list); for(i=0;i<Max;i+) for(j=0;j<Max;j+) p->costij=INF; /初始点的所有路径中各点到其他点的距离为无穷大 p->edgesij=0; /初始化每2个顶点之间没有边 printf("n请输入无向图的顶点数n，和其边数e,格式：n e nn"); scanf("%d %d",&n,&e); printf("n请输入边与边之间的关系，格式：顶点序号-权值-顶点序号n"); /初始化矩阵 for(i=0;i<e;i+) scanf("%d %d %d",&s,&weight,&j); p->costsj=weight; p->costjs=weight; p->edgessj=1; /当俩个顶点之间距离小于INf，则标记有边 p->edgesjs=1; return p; /*哈密尔顿回路寻找函数*/ int search(MG p) int i,k=0,l=0; /l用来用来计回路总数 int *s=new int;/s用来标记是否遍历的顶点，b标记顶点标号 int *b=new int; for(i=0;i<n;i+) si=0; bi=-1; /对sn,bn进行初始化 s0=1; /从0号开始遍历寻找 bk=0; bk+1=bk+1; /顶点号累加 k+; do /主循环 while(bk<n) if(k=0) sbk=1; break; else if(sbk=0&&p->edgesbkbk-1=1) /当顶点未被遍历且与刚遍历的顶点之间有边，则退出当下循环 sbk=1; break; else bk+; /条件不满足，则顶点号累加继续寻找 if(bk>=n) /当顶点号大于N，则对回路数统计，输出 if(k=0) printf("n 图中所含回路个数为:"); printf("%dn",l); return l; else /如果不满足前一个条件，则退回前一个顶点进行重新遍历 sbk-1=0; bk-1=bk-1+1; k-; else if(k=n-1&&p->edgesbkb0!=1) /当最后一个顶点与起始顶点没有路径，则退回前一个顶点重新寻找 sbk-1=0; bk-1=bk-1+1; k-; else if(k=n-1&&p->edgesbkb0=1) /当寻找成功时，存储顶点，然后退回一步进行再遍历 for(i=0;i<n-1;i+) ali=bi; ali+1=bk; l+; sbk=0; sbk-1=0; bk-1=bk-1+1; k-; else /当顶点号不大于N，则继续按照之间思路进行寻找 i=0; while(i<n &&(p->edgesbk i=0|si=1) i+; bk+1=i; k+; while(1); /*对遍寻的结果进行筛选，判断是否有哈密尔顿回路，如有求取最短回路*/ void shaixuan(int l,MG p) int minMax; int sum=0; int i,j,r; int r1,r2; if(l=0) printf("n 此无向图不存在哈密尔顿回路n"); else for(j=0;j<l;j+) sum=0; for(i=0;i<n-1;i+) /对回路求路径长 r1=aji; if(i=n-2) r2=aji+2; else r2=aji+1; printf("%d %dn",r1,r2); sum=sum+p->costr1r2; r2=ajn; r1=aj0; sum=sum+p->costr1r2; minj=sum; /存储路径长 sum=min0; r=0; for(j=1;j<l;j+) /对路经长比较 if(minj<sum) sum=minj; r=j; printf("n 无向图所有哈密尔顿回路如下：nn"); for(i=0;i<l;i+) printf(" 哈密尔顿回路%d 路径长是%dnn",(i+1),mini); printf(" 其经由的点为："); for(j=0;j<n-1;j+) printf("%d->",aij); printf("%dn",aij+1); printf("n"); printf("n 此无向图的最短哈密尔顿回路路径长是%dn",sum); printf("n 其经由的点为："); for(j=0;j<n-1;j+) printf("%d->",arj); printf("%dn",arj+1); /*主函数*/ void main() LARGE_INTEGER BegainTime ; LARGE_INTEGER EndTime ; LARGE_INTEGER Frequency ;QueryPerformanceFrequency(&Frequency);MG p;int l; printf(" 此程序用于低于100个顶点以下的无向图寻找哈密尔顿回路n"); printf("n 欢迎使用n");p=chushihua(); QueryPerformanceCounter(&BegainTime) ;l=search(p); shaixuan(l,p); QueryPerformanceCounter(&EndTime) ; printf("程序运行时间为：%ldn",(EndTime.QuadPart - BegainTime.QuadPart )*1000 / Frequency.QuadPart) ;5.系统实现
