10.3778/j.issn.1002-8331.2008.35.014
高效的求解TSP问题的近似算法
提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解.此算法的时间复杂度为O(n3).而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O(n4).经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低.利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%.
旅行商问题、近似算法、变换矩阵
44
TP301.6(计算技术、计算机技术)
2009-02-24(万方平台首次上网日期,不代表论文的发表时间)
共4页
46-49