摘要： 在文献[1]的基础上定义了狭义TSP。提出了6类边权亏损,指出了几何解的演化逻辑决定数值解的收敛性。新算法的时间复杂性为O(n3),算例表明,解的质量一般不大于1.05倍TSPLIB公布的最优解。

关键词: 狭义TSP, 几何解演化逻辑, 边权亏损

Abstract: A defination is given based on the reference[1].The six categories boundaries weight loss are first proposed. It is pointed out that theevolution logic of the geometric solution determines the convergence of the digital solution. The time complexity of the new algorithom is O(n3).The computation example demonstrates that the quality of the solution is generally not bigger than the 1.05 times of the optimal solution publiced byTSPLIB.

中图分类号: 

• TP301.6