文档介绍：红河学院工学院课程设计报告专业:计算机科学与技术年级:学号:姓名: 成绩: 红河学院工学院编制说明1、本报告供学生课程设计时使用。2、学生应认真阅读所学课程配套的相关资料。3、课程设计报告里面的内容要手工填写,以备存档使用(源程序可打印)。4、课程设计的总评成绩根据课程的性质,按一定比例计入该门课程成绩。5、报告中的“设计方法、设计技术路线、设计成果及总结分析”中的内容是评分的主要依据,如果不够书写,可以自行添加附页。6、按规定的时间提交报告给教师评定成绩,由任课教师交到工学院存档。课程设计目录课程名称:数据结构与算法任务序号任务名称起止页码1TSP问题3~14 设计任务(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大到一定程度后是不可解的。本实验只要求近似解,可以采用贪心法求解:任意选择某个城市作为出发点,然后前往最近的未访问的城市,直到所有的城市都被访问并且仅被访问一次,最后返回到出发点。为便于查找离某顶点最近的邻接点,可以采用邻接矩阵存储该图。算法用伪代码描述如下:;,直到所有顶点都被访问:=最后一个被访问的顶点;;;;采用的设计方法、设计技术路线:(包括本任务的总体安排和进度、采用的设计方法和步骤以及任务流程图、可能遇到的问题和解决的方法)任务总体安排:2014-11-10~2014-12-13完成课程设计所要求的全部任务。进度安排:2014-11-10~2014-11-20:上网查找与题目相关的资料,并重点阅读课本上的相关知识。2014-11-21~2014-11-28:对问题进行抽象,得到描述问题的算法,编写出程序。2014-11-29~2014-12-5:设计完整的程序进行演示。2014-12-6~2014-12-10:对设计进行总结分析。2014-12-11~2014-12-13:填写课程设计手册,并提交指导教师。一、:一个旅行家要穿过多个城市,已知城市个数,以及城市间距,每个城市经历且只经历一次,求出最短路径解和最短路径长度。:输入城市数目N为正整数,城市间距离按邻接矩阵方式排列输入,最小值为0,共有N*N个数值;输出最优解和最优值。:可能遇到的问题:(1)由于参考资料有限,以及自身对程序设计的学****不足,使得在程序中对某些方面的操作可能不符合要求。(2)程序中的算法结构单一,考虑不全,可能不能处理一些特殊问题。解决的方法:(1)多看一些相关知识的参考例子,并对其仔细揣摩,深入了解其含义,掌握其运用的方法;还可以多上网查看和研究一些相似的例子,勤于思考,揣摩创新,善于借鉴他人的成果。(2)根据自身的能力,编写出既严密,又清楚易懂的程序。设计成果及总结分析:(设计成果包括程序清单、测试数据、指定的功能模块说明、设计说明,程序清单可打印,总结分析要手写)功能模块:主函数:intmain()主要由以下函数构成(函数的功能在程序清单中说明):intDistanceMin(int*p);voidCreatArry();voidCreateMatrix();voidTSP();核心源程序清单#include<>#include<>int*choiced;//定义为全局,所有函数都能访问int**matrix;//定义二级指针,操作矩阵intn;//节点数intDistanceMin(int*p);//返回当前距离最短节点对应下标v