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

Efficient approximation algorithm for TSP

作　　者：沈庆涛[1] 张振宇[1] 

机构地区：[1]新疆大学信息科学与工程学院计算机系

出　　处：《计算机工程与应用》2008年第35期46-49,共4页Computer Engineering and Applications

摘　　要：提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解。此算法的时间复杂度为O(n3)。而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O(n4)。经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低。利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%。This paper proposes a new approach based on the matrix transformation,which can approximately transform the TSP problem to a lower TSP problem and achieve the final solution by recursive algorithm.The time complexity of this algorithm is O（n^3）.And then,the algorithm is improved while time complexity is O（n^4）.It is indicated by experimention that the outcome of this algorithm is very efficient,especially in those problem who fulfil triangle inequation.This paper tests the algorithm with the data in TSPLIB,and the error of the outcome not more than 10%.

关 键 词：旅行商问题 近似算法 变换矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]