高效的求解TSP问题的近似算法

• 作者: 张振宇 沈庆涛
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 旅行商问题 近似算法 变换矩阵
• 年，卷（期）: 2008,（35）
• 所属期刊栏目: 理论研究
• 页码范围: 46-49
• 页数: 4页
• 分类号: TP301.6
• 字数: 3560字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.35.014

摘要

提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解.此算法的时间复杂度为O(n3).而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O(n4).经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低.利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张振宇	新疆大学信息科学与工程学院计算机系	70	209	8.0	11.0
2	沈庆涛	新疆大学信息科学与工程学院计算机系	2	13	2.0	2.0