狭义TSP几何解的演化逻辑与算法  

Evolution Logic and Algorithm for Narrow TSP Geometric Solution

作　　者：王锦彪[1] 

机构地区：[1]中国民航学院计算机科学与技术学院,天津300300

出　　处：《计算机工程》2005年第14期77-79,230,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(69732010);国航天津分公司重点科研基金资助项目

摘　　要：在文献[1]的基础上定义了狭义TSP。提出了6类边权亏损,指出了几何解的演化逻辑决定数值解的收敛性。新算法的时间复杂性为O(n3),算例表明,解的质量一般不大于1.05倍TSPLIB公布的最优解。A definition is given based on the reference. The six categories boundaries weight loss are first proposed. It is pointed out that the evolution logic of the geometric solution determines the convergence of the digital solution. The time complexity of the new algorithm 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 of TSPLIB.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]