求解旅行商问题的近似多项式算法  

A polynomial approximation algorithm for the traveling salesman problem

作　　者：高尚[1] 房靖[1] 

机构地区：[1]江苏科技大学计算机科学与工程学院,江苏镇江212003

出　　处：《智能系统学报》2010年第4期342-346,共5页CAAI Transactions on Intelligent Systems

基　　金：江苏省高校自然科学基础研究资助项目(08KJB520003);浙江大学CAD&CG国家重点实验室开放课题资助项目(A0704)

摘　　要：旅行商(TSP)问题是一个典型的组合优化问题,易于描述却难于求解.对于大规模TSP问题,目前仍没有非常有效的方法.针对弹性网络算法在求解旅行商问题中时间性能方面的不足,提出了一种快速的求解算法.在弹性网络算法基础上,提出了求解旅行商问题的扩张方法和收缩方法,它们时间复杂性低于O(N3),经过比较扩张方法的效果比较理想.在扩张方法的基础上,提出随机扩张方法和完全扩张方法,完全扩张方法的时间复杂性低于O(N4),仍然是一个多项式算法.实例表明,完全扩张方法是一个快速且有效的算法.The traveling salesman problem （TSP）is a typical combinational optimization problem which is easy to describe and hard to solve. For large-scale TSP problems,an effective solution has yet to be found. To improve the time performance of the elastic net method in solving large scale TSPs,faster algorithms were investigated. Use of the elastic net method,the expansion method and the shrink method were proposed. The time complexities of these algorithms were less than O（N3）. After comparison and analysis it was clear that the results of the expansion method were comparatively ideal. Based on analysis of the expansion method,a stochastic expansion method and a complete expansion method were developed. The time complexity of the complete expansion method was less than O（N4）,and it was still a polynomial algorithm. Practical examples showed that the complete expansion method is fast and efficient.

关 键 词：扩张方法 收缩方法 旅行商问题 

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