第5卷第4期 智能系统学报 Vol.5 No.4 2010年8月 CAAI Transactions on Intelligent Systems Aug.2010 doi:10.3969/i.issn.16734785.2010.04.010 求解旅行商问题的近似多项式算法 高尚，房靖 (江苏科技大学计算机科学与工程学院，江苏镇江212003)】 摘要：旅行商问题是一个典型的组合优化问题，易于描述却难于求解.对于大规模SP问题，目前仍未有非常有效 的方法.针对弹性网络算法在求解旅行商问题中时间性能方面的不足，提出了一种快速的求解算法.在弹性网络算 法基础上，提出了求解旅行商问题的扩张方法和收缩方法，它们时间复杂性低于O(W),经过比较扩张方法的效果 比较理想.在扩张方法的基础上，提出随机扩张方法和完全扩张方法，完全扩张方法的时间复杂性低于O(N),仍然 是一个多项式算法.实例表明，完全扩张方法是一个快速且有效的算法. 关键词：扩张方法；收缩方法；旅行商问题 中图分类号：TP301.6文献标识码：A文章编号：16734785(2010)040342-05 A polynomial approximation algorithm for the traveling salesmen problem GAO Shang,FANG Jing (School of Computer and Engineering,Jiangsu University of Science and Technology,Zhenjiang 212003,China) Abstract: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 0(N).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 0(N),and it was still a polynomial algorithm.Practical examples showed that the complete expansion method is fast and efficient. Keywords:expansion method;shrink method;traveling salesman problem 旅行商问题(traveling salesman problem)可以描多项式方法 述为有一个推销员从某城市出发走遍所有的城市， 且每个城市只能走一次，最后返回原处，如何选择路 1扩张方法 线使所走路程最短.TSP问题是一个NP完全问题， 1987年，R.Durbin和D.Willshaw提出了一种 对于一个V个城市的TSP问题，可能的路径数是一 被称为弹性网络的新模型1o11来求解TSP问题.这 个组合数(N-1)/2,随着城市数目N的增大，问 一模型考虑的是欧氏空间中的TSP问题，它把一条 题的规模呈指数式增大.目前求解TSP问题的主要 TSP可行路径看作是从一条由M个节点构成的闭 方法有模拟退火算法14、遗传算法1s6、,启发式 合路径到TSP城市的映射.这条闭合路径被称为 搜索法、Hopfield神经网络算法、蚁群算法[891等. “弹性带”(elastic band),一般来说取M=2.5N.当 本文在弹性网络算法的基础上提出2种简单的近似 对于每一个城市都有一个节点与它重合时，“弹性 带”的总长度就是TSP路径总长度的一个近似.弹 收稿日期：200907-13. 性网络算法的思想就是不断调整这些节点的位置， 基金项目：浙江大学CAD&CG国家重点实验室开放课题(A0704);江 苏省高校自然科学基础研究课题(08KB520003). 使得“弹性带”在覆盖所有城市的同时，总的长度尽 通信作者：高尚.E-mail:gao_hang@hotmial.com 可能小.弹性网络算法通过2种作用力来控制弹性