数据结构课程设计 设计说明书 题目 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大到一定程度后是不可解的
本实验只要求近似解，可以采用贪
