数据结构程序设计TSPn城市旅行问题

学号数据结构课程设计设计说明书TSP起止日期：20XX年12月12日至20XX年12学生姓名班级成绩指导教师(签字)电子与信息工程系20XX年12月16日

天津城市建设学院课程设计任务书20XX—20XX学年第1学期电子与信息工程系软件工程专业班级课程设计名称：数据结构课程设计设计题目：Tsp完成期限：自20XX年12月12日至20XX年12月16日共1周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容6．TSP问题1)问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2)基本要求(1)上网查找TSP问题的应用实例；(2)分析求TSP问题的全局最优解的时间复杂度；(3)设计一个求近似解的算法；(4)分析算法的时间复杂度。3)设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n大到一定程度后是不可解的。本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：1.任意选择某个顶点v作为出发点；2.执行下述过程，直到所有顶点都被访问：2.1v=最后一个被访问的顶点；2.2在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j；2.2访问顶点j；3.从最后一个访问的顶点直接回到出发点v；【思考题】上网查找TSP问题的应用实例，写一篇综述报告。四、参考文献1．王红梅．数据结构．清华大学出版社2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社一、需求分析(程序的功能、输入输出的要求)任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。要求这时遍历各城市的距离为最短距离。输入城市间的距离，把本城市到本城市距离输入为99999。要求输入的为整数。结果为输出最短路径和遍历的最短距离，要求为整数。二、问题求解TSP问题，要求先画一个旅行的线路图的图示，然后假设有个人，遍历所有的旅行的城市，考虑所有可能的旅行路线，从中选择最佳的一条。突出其中用到的中间数据是：数组形式，初始数据是各个城市间的距离。假设我们进行我们的旅游计划，共五个城市，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。要求这时遍历各城市的距离为最短距离。当我们要求整体的最优解时，可以从它的局部最优解求的，抱着这样的思想我们从起始城市1出发比较与之最近的城市的距离是2（2号城市），由于不能返回，所以从2号城市继续寻找与之最近的城市（1号城市除外）的距离是4（3号城市），以此类推，最终在返回起始城1。补充：上面的最短距离要记录下来，求和，则得到最短路径。如果城市数目增加，则重复第一个城市到第二个城市这个步骤。在计算机中实现这个程序，则要记住每个最优城市的标号。存放数组中，再输出最优路径。城市1城市1城市567城市5城市4城市452893城市2城市35城市2城市34三、总体设计程序设计组成框图:TSPTSP循环遍历找到与起始城市最近的城市序号。用flag[]保存，用min[]保存最短路径。用sum+=min[]求出最短路径输出flag[],得到最佳路径输入各城市间的距离循环遍历找到与起始城市最近的城市序号。用flag[]保存，用min[]保存最短路径。用sum+=min[]求出最短路径输出flag[],得到最佳路径输入各城市间的距离流程图开始开始输入城市的个数cityNum和城市间的距离输入城市的个数cityNum和城市间的距离mmin[i]>=d[][j]?J++J++yesMMin[i]=d[][j]FFlag[i]=jSum=0Sum=0Sum+=min[i]i<cityNum?输出最短路径Flag[i]输出最短距离sumyesYes输出最短路径Flag[i]输出最短距离sum四、详细设计publicvoidinitDistance()作用：该方法是存储个城市间的距离，及城市的数目。publicvoidsum()作用：该方法是求各个城市间的最短路径和，并且记录下最佳的旅行路径。补充说明：每次都要起初的最小距离min[i]=99999;去和临近的城市去比较距离min[i]>=distance[flag[k]][j]，这样min[i]肯定会被覆盖，此时在根据for（j++）循环逐次比较，得出最小的min[i]，用flag[k+1]去记下这个城市的编号。再用for循环，输出最佳路径flag[]。publicstaticvoidmain(String[]args){}作用：主函数，在主函数中调用各种方法。例如：sum()方法，initDistance()方法。五、调试与测试测设过程中for(inti=0;i<cityNum-1;i++){ min[i]=99999;for(intj=0;j<cityNum;j++){ if(min[i]>=distance[flag[k]][j]){ min[i]=distance[flag[k]][j]; flag[k+1]=j; }Min[i]我把第二个for循环的i写成了j，没有错误，但是结果不对，导致我改了一下午。细心很重要啊。六、关键源程序清单和执行结果代码： importjava.util.Scanner;publicclassTsp{ intcityNum; int[][]distance=newint[10][10]; intmin[]=newint[10]; intflag[]=newint[10]; publicvoidinitDistance(){ System.out.println("请输入城市的数目"); Scannerinput=newScanner(System.in); cityNum=input.nextInt(); /* *for(inti=0;i<cityNum;i++){//为了输入的更快当

i=j时自动的赋值为0 *distance[i][i]=0;} */ for(inti=0;i<cityNum;i++){//由于二维数组的存储

是对称的可以用压缩存储的方法初始化 for(intj=0;j<cityNum;j++){ System.out.println("请输入第"+i+"城市

到第"+j+"城市之间的距离"); distance[i][j]=input.nextInt(); } } intcount=0; for(inti=0;i<cityNum;i++){ for(intj=0;j<cityNum;j++){ System.out.print(distance[i][j]); count++; if(count%cityNum==0){ System.out.println(); } } } } publicvoidsum(){ intk=0; intx=0; flag[0]=0; for(inti=0;i<cityNum-1;i++){ min[i]=99999; for(intj=0;j<cityNum;j++){ if(min[i]>=distance[flag[k]][j]){ min[i]=distance[flag[k]][j]; flag[k+1]=j; } } k++; x=0; //对称的点变成99999，防止往回遍历。 while((k-x)!=0){ distance[flag[k]][flag[k-x-1]]=99999;

x++; } } System.out.println("最优路径："); for(inti=0;i<cityNum;i++){ System.out.print(flag[i]); } System.out.println(flag[0]); intsum=0; for(intm=0;m<cityNum-1;m++){ sum=sum+min[m]; } sum=sum+distance[flag[0]][flag[cityNum-1]]; System.out.println("最优路径长度为："+sum); } publicstaticvoidmain