数据结构与算法分析 2算法设计报告书班级 惠普测试 学号 姓名 指导老师 庞志永 算法设计项目名称：满足三角不等式得 TSP 问题得近似算法1、问题描述2、基本要求（1)设计满足三角不等式得 TS Ｐ问题得近似性能比小于 2 或 1、5 得多项式时间近似算法,并选择适当得编程语言在计算机上实现。（２）程序能够正常运行，计算结果正确,满足设计要求。3、算法描述４、模块划分(仅供参考）(1）描述及输入原始数据模块(２）求解最小生成树模块（3）构造欧拉图模块（4）搜索欧拉回路模块(5）抄近路计算模块(6）存储及输出结果模块5、本课程设计中遇到得关键问题及其解决方法ﻩ课题关键：在给定一系列城市与每对城市之间得距离得情况下,求解访问每一座城市一次并回到起始城市得最短回路. ﻩ解答本课题得思路：以最小生成树 T 求解旅游回路:复制树得每条边构建欧拉图，运用深度优先搜索寻找欧拉图得欧拉回路，而树得深度优先搜索序列与此欧拉回路相同，可用深度优先搜索算法优化求解欧拉回路与抄近路算法得过程.6、运行结果及其相关描述要求实例中城市得数量在 20—1 ０ 0 之间。命令行输入此次实验验证 2 ０个城市即为 20 个顶点,１ 90 条边1 ２ 2 1 3 3 2 3 2 1 4 ３ 2 4 ３ 3 4 ２ 1 5 ３ 2 5 3 3 5 3 4 ５ 2 1 ６ ３ ２ 6 3 3 6 ３ ４ 6 3 5 ６ 2 １ 7 ３ 2 ７ 3 ３ 7 3 4 7 3 5 ７ 3 6 7 2 1 8 ３ ２ ８ 3 3 8 3 4 8 3 ５ 8 3 6 8 3 7 8 2 1 ９ ３ 2 9 3 3 9 3 4 9 ３ ５ 9 3 6 ９ ３ ７ 9 ３ 8 9 2 １ 1０ 3 2 1０ ３ 3 １０ 3 ４ 10 3 ５ １0 3 6 1０ ３ 7 1０ ３ 8 1０ 3 ９ １0 2 １ 11 3 2 1１ ３ 3 1１ 3 4 11 3 ５ １１ 3 6 1１ 3 7 １1 3 8 11 3 9 11 ３ 10 11 ２ １ 12 3 2 12 3 ３ 12 3 4 12 3 5 1２ 3 6 12 3 ７ １2 ３ 8 １2 3 9 １2 3 10 1２ 3 11 12 2 1 １３ ３ ２ 1３ 3 3 １３ 3 ４ 1３ 3 5 １3 ３ ６ 13 ３ 7 13 3 ８ 13 3 9 1３ 3 10 1３ 3 11 1３ 3 12 13 2 1 1４ 3 2 １４ 3 3 １4 3 4 14 ３ 5 14 3 6 １4 ３ 7 1４ 3 8 14 3 9 14 ３ 10 14 3 1１ 1４ 3 1２ 14 3 1３ 14 2 1 15 3 2 1５ ３ 3 15 3 4 ...
