Approximate algorithm for traveling salesman problem based on graph theory

doi:10.3778/j.issn.1002-8331.2009.32.016

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (32): 51-52.DOI: 10.3778/j.issn.1002-8331.2009.32.016

• 研究、探讨 • Previous Articles Next Articles

Approximate algorithm for traveling salesman problem based on graph theory

XU Jin-xing，WU Su-ping

College of Mathematics and Computer，Ningxia University，Yinchuan 750021，China

Received:2008-07-29 Revised:2008-10-21 Online:2009-11-11 Published:2009-11-11
Contact: XU Jin-xing

旅行售货员问题的图论近似算法

许金星，吴素萍

宁夏大学数学与计算机学院，银川 750021

通讯作者: 许金星

Abstract

Abstract: The relationship between the Hamilton circuit and the Traveling Salesman Problem is discussed.On the basis of this and the approximate algorithm of shortest path of the complete graph theory，a new approximate algorithm of TSP is proposed.Analyses and examples show that the approximate algorithm is effective.

Key words: graph theory, Hamilton circuit, Traveling Salesman Problem（TSP）, approximate algorithm

摘要： 讨论了旅行售货员问题和图论中的哈密顿回路之间的关系，在此基础上结合图论中关于完全图最短路径的近似算法得到旅行售货员问题的一种近似算法。通过分析及实例验证了所提出的算法的可行性及有效性。

关键词: 图论, 哈密顿回路, 旅行售货员问题, 近似算法

CLC Number:

TP311

XU Jin-xing，WU Su-ping. Approximate algorithm for traveling salesman problem based on graph theory[J]. Computer Engineering and Applications, 2009, 45(32): 51-52.

许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.

[1]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[2]	MENG Yun, HU Xin, DAI Liang, YU Lei. Connectivity Improvement Resource Allocation Algorithm in Interference Vehicular Networks [J]. Computer Engineering and Applications, 2019, 55(7): 9-15.
[3]	CHEN Jia, YOU Xiaoming, LIU Sheng, LI Juan. Entropy-Game Based Multi-Population Ant Colony Optimization [J]. Computer Engineering and Applications, 2019, 55(16): 170-178.
[4]	ZHAO Yawen, XIONG Ruiping, QIAO Zhi, LIANG Qiqi, LUO Yong. Improved Polymorphic Ant Colony Algorithm with Predatory Search Strategy [J]. Computer Engineering and Applications, 2019, 55(14): 115-121.
[5]	LIU Kang1, ZHANG Xueying1, LI Fenglian1, TIAN Yuchu1，2. Graph partitioning method for social networks based on communication load balancing [J]. Computer Engineering and Applications, 2018, 54(4): 66-71.
[6]	BAI Jingbo, LI Hongwei, CHEN Liang, FENG Yufang, LIU Jianyong. Double-chain quantum-inspired ant colony system and its application [J]. Computer Engineering and Applications, 2018, 54(21): 1-6.
[7]	XU Xiaoping, ZHANG Dongjie. Solving traveling salesman problem based on monkey algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 144-148.
[8]	GONG Chen, WU Lifang, LIU Weichan, ZHANG Xin. Choosability of signed graphs without certain minors [J]. Computer Engineering and Applications, 2018, 54(16): 55-58.
[9]	LIU Weichan, ZHANG Xin. Equitable vertex arboricity of outer-1-planar graphs [J]. Computer Engineering and Applications, 2018, 54(10): 51-53.
[10]	DUAN Yanming1, XIAO Huihui1，2. Improved fruit fly algorithm for TSP problem [J]. Computer Engineering and Applications, 2016, 52(6): 144-149.
[11]	WAN Zhengyi, PENG Yuxu. Improved quantum ant colony algorithm for Traveling Salesman Problem [J]. Computer Engineering and Applications, 2016, 52(22): 59-63.
[12]	LI Xu, LIU Zhengyan. Fuzzy self-adaptive ant colony algorithm based on cloud model [J]. Computer Engineering and Applications, 2016, 52(2): 24-27.
[13]	CHEN Jizhen, NING Aibing, ZHI Zhibing, HU Linlin, ZHANG Huizhen. Exact algorithm for maximum independent set problem in graph theory [J]. Computer Engineering and Applications, 2016, 52(1): 20-22.
[14]	MA Fuxiang, MA Xiujuan. Improved genetic algorithm based on double mutation operators [J]. Computer Engineering and Applications, 2014, 50(13): 62-65.
[15]	ZHANG Han1, HE Dongjian2. Image segmentation approach by combining texture information and graph theory [J]. Computer Engineering and Applications, 2014, 50(1): 180-184.

Approximate algorithm for traveling salesman problem based on graph theory

旅行售货员问题的图论近似算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics