《数据结构课程设计贪心法求解tsp问题》由会员分享，可在线阅读，更多相关《数据结构课程设计贪心法求解tsp问题（3页珍藏版）》请在金锄头文库上搜索。
1、中南民族大学计算机科学学院本科课程设计任 务 书设计名称： 贪心法求解TSP问题 指导教师： 吴立锋 下达时间： 2014-10-17学生姓名： 张思齐 学 号： 2012213810年级专业： 2012级网络工程一、 课程设计的基本要求利用数据结构课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C+语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。具体要求如下
2、：1、 对现实复杂问题中的数据对象特性及组织方法进行分析和研究，设计适当的数据逻辑结构、存贮结构以及相应运算操作，把现实世界问题建模转化为计算机内部表示并进行处理。2、 采取模块化方式进行程序设计，要求程序的功能设计、数据结构设计及整体结构设计合理。学生也可根据自己对题目的理解增加新的功能模块（视情况可另外加分）。3、 系统以菜单界面方式（至少采用文本菜单界面，如能采用图形菜单界面更好）工作，运行界面友好，演示程序以用户和计算机的对话方式进行，利用文件进行数据的提取与存储。4、 程序算法说明清晰，理论分析与计算正确，运行情况良好，实验测试数据无误，容错性强（能对错误输入进行判断控制）。5、 编
3、程风格良好（包括缩进、空行、适当注释、变量名和函数名见名知意，程序容易阅读等）；6、 写出规范的课程设计报告，具体要求见相关说明文档。二、 课程设计的主要内容题目描述：TSP（Traveling Salesman Problem ）是指：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。类似的问题有： 中国邮递员问题（Chinese Postman Problem CPP） 一个邮递员从邮局出发，到所辖街道投递
4、邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？配送路线问题（Route of Distribution） TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。功能要求及说明：（1）将上图存入文件，运行时从文件读取数据；（2）输出所求的环路，并计算该环路上的总代价；（3）采用模块化设计。 提示：求解TSP问题至少有两种贪心策略是合理的：（1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市，具体求解过程举例如下： （2）最短链接策略
5、：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个简单回路。因此，当从剩余边集E中选择一条边(u, v)加入解集合S中，应满足以下条件： 边(u, v)是边集E中代价最小的边； 边(u, v)加入解集合S后，S中不产生回路； 边(u, v) 加入解集合S后，S中不产生分枝；具体求解过程举例如下： 三、课程设计的进程安排12014年10月17日：布置并下达课程设计题目。22014年10月24日之前：联系指导教师，理解课程设计题目及相关要求，查阅相关资料，进行课程设计（地点：9-503，9-504）。32014年10月24日至11月21日（第8周-第12周）：课程设计源程序的调试、修改与检查，书写课程设计报告（地点：计算机科学学院实验机房）。42014年11月21日之前：上交、检查设计报告（地点：计算机科学学院实验机房）。指导教师：吴立锋 2014年 10月17日- 3 -
