数据结构与算法分析(共7页).doc

精选优质文档-倾情为你奉上数据结构与算法分析2算法设计报告书班级 惠普测试 学号 姓名 指导教师 庞志永 算法设计项目名称：满足三角不等式的TSP问题的近似算法1.问题描述2.基本要求(1)设计满足三角不等式的TSP问题的近似性能比小于2或1.5的多项式时间近似算法，并选择适当的编程语言在计算机上实现。(2)程序能够正常运行，计算结果正确，满足设计要求。3.算法描述4.模块划分(仅供参考)(1)描述及输入原始数据模块(2)求解最小生成树模块(3)构造欧拉图模块(4)搜索欧拉回路模块(5)抄近路计算模块(6)存储及输出结果模块5.本课程设计中遇到的关键问题及其解决方法课题关键：在给定一系列城市和每对城市之间的距离的情况下，求解访问每一座城市一次并回到起始城市的最短回路。 解答本课题的思路：以最小生成树T求解旅游回路：复制树的每条边构