[1]高 尚,房 靖.求解旅行商问题的近似多项式算法[J].智能系统学报,2010,5(4):342-346.
GAO Shang,FANG Jing.A polynomial approximation algorithm for the traveling salesman problem[J].CAAI Transactions on Intelligent Systems,2010,5(4):342-346.
点击复制
GAO Shang,FANG Jing.A polynomial approximation algorithm for the traveling salesman problem[J].CAAI Transactions on Intelligent Systems,2010,5(4):342-346.
求解旅行商问题的近似多项式算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
5
期数:
2010年第4期
页码:
342-346
栏目:
学术论文—人工智能基础
出版日期:
2010-08-25
- Title:
- A polynomial approximation algorithm for the traveling salesman problem
- 文章编号:
- 1673-4785(2010)04-0342-05
- Keywords:
- expansion method; shrink method; traveling salesman problem
- 分类号:
- TP301.6
- 文献标志码:
- A
- 摘要:
- 旅行商(TSP)问题是一个典型的组合优化问题，易于描述却难于求解.对于大规模TSP问题，目前仍没有非常有效的方法.针对弹性网络算法在求解旅行商问题中时间性能方面的不足，提出了一种快速的求解算法．在弹性网络算法基础上，提出了求解旅行商问题的扩张方法和收缩方法，它们时间复杂性低于O(N3)，经过比较扩张方法的效果比较理想.在扩张方法的基础上，提出随机扩张方法和完全扩张方法，完全扩张方法的时间复杂性低于O(N4)，仍然是一个多项式算法.实例表明，完全扩张方法是一个快速且有效的算法.
- Abstract:
- The traveling salesman problem (TSP）is a typical combinational optimization problem which is easy to describe and hard to solve. For largescale 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.
- 参考文献/References:
-
［1］邢文循，谢金星.现代优化计算方法［M］.北京：清华大学出版社，1999：90-129.
［2］高国华，沈林成，常文森. 求解TSP问题的空间锐化模拟退火算法［J］.自动化学报，1999,25(3):425-428.
GAO Guohua, SHEN Lincheng, CHANG Wensen. Using simulated annealing algorithm with search space sharpening to solve traveling salesman problem［J］. Acta Automatica Sinica, 1999， 25(3): 425-428.
［3］KIRKPATRICK S, GELATT J R，VECCHI J R. Optimization by simulated annealing［J］. Science， 1983, 220: 671-680.
［4］康立山，谢云，尤矢勇，等.模拟退火算法［M］.北京：科学出版社，1994：150-151.
［5］谢胜利，唐敏，董金祥.求解TSP问题的一种改进的遗传算法［J］.计算机工程与应用，2002,38（8）：58-60.
XIE Shengli, TANG Min, DONG Jinxiang. An improved genetic algorithm for TSP problem［J］.Computer Engineering and Applications, 2002, 38（8）： 58-60.
［6］喻镝，凌捷，谢晓峰.用遗传算法求解CTSP［J］.广东工业大学学报，2000, 17（5）： 52-55.
?YU Di, LING Jie, XIE Xiaofeng. Solving CTSP with genetic algorithm［J］. Journal of Guangdong University of Technology, 2000， 17(5)： 52-55.
［7］张立明.人工神经网络的模型及其应用［M］.上海:复旦大学出版社，1994：97-98.
［8］吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法［J］.计算机研究与发展，1999,36(10)： 1240-1245.
WU Qinghong, ZHANG Jihui, XU Xinhe. An ant colony algorithm with mutation features［J］. Journal of Computer Research and Development, 1999, 36(10)： 1240-1245.
［9］马良，项培军.蚂蚁算法在组合优化中的应用［J］.管理科学学报，2001, 4(2)： 32-37.
MA Liang, XIANG Peijun. Applications of the ant algorithm to combinatorial optimization［J］.Journal of Management Sciences in China, 2001， 4(2)： 32-37.
［10］DURBIN R, WILLSHAW D. An analogue approach to the traveling salesman problem using an elastic net method［J］. Nature, 1987, 326: 689-691.
［11］白艳萍,胡红萍.一个改进的弹性网络算法求解TSP问题［J］.华北工学院学报,2005, 26(4): 235-238.
BAI Yanping, HU Hongping. A modified elastic net algorithm for traveling salesman problem［J］. Journal of North China Institute of Technology, 2005, 26(4): 235-238.
备注/Memo
收稿日期：2009-07-13.
基金项目：
江苏省高校自然科学基础研究资助项目（08KJB520003）；
浙江大学CAD&CG国家重点实验室开放课题资助项目(A0704).
通信作者：高 尚.E-mail:gao_shang@hotmial.com.
作者简介：高 尚，男，1972年生，教授，主要研究方向为智能计算等.
更新日期/Last Update:
2010-09-20