数据结构TSP问题贪心法求解

红河学院工学院课程设计报告专业：计算机科学与技术年级：学号：姓名： 成绩：红河学院 工学院编制说 明1、本报告供学生课程设计时使用。2、学生应认真阅读所学课程配套的相关资料。3、课程设计报告里面的内容要手工填写，以备存档使用（源程序可打印）。4、课程设计的总评成绩根据课程的性质，按一定比例计入该门课程成绩。5、报告中的“设计方法、设计技术路线、设计成果及总结分析”中的内容是评分的主要依据，如果不够书写，可以自行添加附页。6、按规定的时间提交报告给教师评定成绩，由任课教师交到工学院存档。课程设计目录课程名称：数据结构与算法任务序号任务名称起止页码1TSP问题314 设计任务（1）任务名称TSP问题班级13计算机科学与技术指导教师地点红河学院成绩学年2014-2015开始日期2014-11-10结束日期2014-12-13组员设计目的及要求：目的：（1）熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 （2）掌握软件设计的基本内容和设计方法，并初步具备进行规范化软件设计能力。要求：（1）首先要分析题目，查阅相关资料。（2）清晰的设计出整个程序的算法思路。（3）按要求编写程序。（4）认真编写课程设计报告。设计内容及基本要求：内容： TSP问题1) 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2)基本要求：(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度。3) 设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为(n!)，当n大到一定程度后是不可解的。本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：1. 任意选择某个顶点v作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j； 2.2 访问顶点j； 3. 从最后一个访问的顶点直接回到出发点v；采用的设计方法、设计技术路线：（包括本任务的总体安排和进度、采用的设计方法和步骤以及任务流程图、可能遇到的问题和解决的方法）任务总体安排：2014-11-102014-12-13完成课程设计所要求的全部任务。进度安排：2014-11-102014-11-20：上网查找与题目相关的资料，并重点阅读课本上的相关知识。2014-11-212014-11-28：对问题进行抽象，得到描述问题的算法，编写出程序。2014-11-292014-12-5：设计完整的程序进行演示。2014-12-62014-12-10：对设计进行总结分析。2014-12-112014-12-13：填写课程设计手册，并提交指导教师。一、需求分析1.程序的功能：一个旅行家要穿过多个城市，已知城市个数，以及城市间距，每个城市经历且只经历一次，求出最短路径解和最短路径长度。2.输入输出的要求：输入城市数目N为正整数，城市间距离按邻接矩阵方式排列输入，最小值为0，共有N*N个数值；输出最优解和最优值。1.程序流程图：可能遇到的问题：（1）由于参考资料有限，以及自身对程序设计的学习不足，使得在程序中对某些方面的操作可能不符合要求。（2）程序中的算法结构单一，考虑不全，可能不能处理一些特殊问题。解决的方法：（1）多看一些相关知识的参考例子，并对其仔细揣摩，深入了解其含义，掌握其运用的方法；还可以多上网查看和研究一些相似的例子，勤于思考，揣摩创新，善于借鉴他人的成果。（2）根据自身的能力，编写出既严密，又清楚易懂的程序。设计成果及总结分析：（设计成果包括程序清单、测试数据、指定的功能模块说明、设计说明，程序清单可打印，总结分析要手写）功能模块：主函数：int main()主要由以下函数构成（函数的功能在程序清单中说明）：int DistanceMin(int *p); void CreatArry(); void CreateMatrix(); void TSP(); 核心源程序清单#include#includeint *choiced; /定义为全局，所有函数都能访问 int* matrix; /定义二级指针，操作矩阵 int n; /节点数 int DistanceMin(int *p); /返回当前距离最短节点对应下标 void CreatArry(); /动态创建标记数组 void CreateMatrix(); /动态创建矩阵 void TSP(); /贪心算法排序 int main()printf(输入城市数：n); scanf(%d,&n);CreateMatrix(); CreatArry(); TSP();return 0;void CreateMatrix() int i=0,j=0; matrix=(int* )malloc (sizeof (int*)*n); /动态创建n行n列矩阵 for (i=0;in;+i)matrixi = (int*)malloc (sizeof (int)*n); printf(输入城市间距离的邻接矩阵：n,n);for(i=0;in;i+) /输入数据到矩阵 for(j=0;jn;j+)scanf(%d,&matrixij); void CreatArry() int i=0; choiced=(int*)malloc(sizeof(int)*n); /动态创建标记数组 choiced0=0;for(i=1;in;i+)choicedi=1; int DistanceMin(int *p)int start=0,min=p0,k=0; while(choicedstart=0) /下标为0的地点跳过，找到开始搜索的位置start+;min=pstart;for(;start=pstart) /如果该位置没有被采纳，并且距离小于min所存距离k=start; /存储该位置下标min=pk;return k;void TSP()int i=0,j=0,s=0; int log=0; printf(最短路径为：n);for(;log%d,i+1,j+1);s=s+matrixij; /累加总距离 i=j; /搜寻位置跳到j printf(n);printf(最短距离为：%dn,s);char wait; /吸收回车符 scanf(%c,&wait);scanf(%c,&wait); 测试数据城市1城市2 1088 118城市3 953 1640 1600 2067城市4邻接矩阵：A=0 1088 118 1640 1088 0 953 1600 118 953 0 2067 1640 1600 2067 0 运行结果： 总结：在程序设计中细心很重要，常常一个符号的错误就需要很长时间的修改。在设计过程中要善于查找资料，认真查看课本。独立完成。数据结构是计算机程序设计的重要理论基础，是计算机科学的核心课程。在这个学期的学习过程中，我们在上学期c语言的基础上进一步的进行了深入