数据结构课程设计 设计说明书 题目 TSP问题贪心算法 起止日期： 2014年 11月 10 日 至 2014 年 11月17日 学生姓名 滕文亮 班级 113301班 成绩 指导教师(签字) 计算机科学与工程学院 2 0 1 4 年1 1 月9 日 课程设计任务书 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 在本课程设计过程中要求学生： （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。 （3）学生在接受设计任务后，根据要求认真完成。 （4）认真编写课程设计报告。 三、设计内容 TSP问题（贪心法求解） 1) 问题描述 所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 2) 基本要求 (1) 上网查找TSP问题的应用实例； (2) 分析求TSP问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法； (4) 分析算法的时间复杂度。 3) 设计思想 对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο (n!)，当n大到一定程度后是不可解的。 4）设计思想 对于TSP 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP 问题的时间复杂度为Ο(n!)，当 n大到一定程度后是不可解的。 本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。 为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下： 1. 任意选择某个顶点 v 作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v =最后一个被访问的顶点； 2.2 在顶点 v 的邻接点中查找距离顶点 v 最近的未被访问的邻接点 j； 2.2 访问顶点 j； 3. 从最后一个访问的顶点直接回到出发点 v ； 四、参考文献 1 . 王红梅，...
