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

学 号 数据结构课程设计 设计说明书 起止日期： 20年 月 日 至 年 月日 学生姓名 班级 成绩 指导教师(签字) 系 年 月日  天津城市建设学院 课程设计任务书 20—2012学年第学期 系 专业 班级 课程设计名称： 设计题目： 完成期限：自 年 月 日至 年 月 日共 周 设计依据、要求及主要内容（可另加附页）： 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 6．TSP问题 1) 问题描述 所谓TSP问题是指旅行家要旅行个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题 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； 【思考题】上网查找TSP问题的应用实例，写一篇综述报告。 四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 一、需求分析(程序的功能、输入输出的要求) 任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。要求这时遍历各城市的距离为最短距离。 输入城市间的距离，把本城市到本城市距离输入为99999。要求输入的为整数。结果为输出最短路径和遍历的最短距离，要求为整数。 二、问题求解 TSP问题，要求先画一个旅行的线路图的图示，然后假设有个人，遍历所有的旅行的城市，考虑所有可能的旅行路线，从中选择最佳的一条。突出其中用到的中间数据是：数组形式，初始数据是各个城市间的距离。假设我们进行我们的旅游计划，共五个城市，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。要求这时遍历各城市的距离为最短距离。当我们要求整体的最优解时，可以从它的局部最优解求的，抱着这样的思想我们从起始城市1出发比较与之最近的城市的距离是2（2号城市），由于不能返回，所以从2号城市继续寻找与之最近的城市（1号城市除外）的距离是4（3号城市），以此类推，最终在返回起始城1。补充：上面的最短距离要记录下来，求和，则得到最短路径。如果城市数目增加，则重复第一个城市到第二个城市这个步骤。在计算机中实现这个程序，则要记住每个最优城市的标号。存放数组中，再输出最优路径。 6 7 5 2 8 9 3 5 4 三、总体设计 程序设计组成框图: 流程图 no