[1]宗德才[],王康康[]. 旅行商问题中巡回路径的数据结构[J].计算机技术与发展,2014,24(12):72-77.
　ZONG De-cai[],WANG Kang-kang[]. Data Structure of Tour for Traveling Salesman Problem[J].,2014,24(12):72-77.
点击复制

 旅行商问题中巡回路径的数据结构()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
24
期数:
2014年12期
页码:
72-77
栏目:
智能、算法、系统工程
出版日期:
2014-12-10

文章信息/Info

Title:
 Data Structure of Tour for Traveling Salesman Problem
文章编号:
1673-629X（2014)12-0072-06
作者:
 宗德才[1] ; 王康康[2]
 1.常熟理工学院 计算机科学与工程学院；2.江苏科技大学 数理学院
Author(s):
 ZONG De-cai[1] ; WANG Kang-kang[2]
关键词:
 ; 旅行商问题; 局部启发式算法; 数组; 伸展树; 两级树
Keywords:
 ; traveling salesman problem; local heuristic algorithm; array splay; tree two-level tree
分类号:
TP311.12
文献标志码:
A
摘要:
 旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序，并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序，但是最坏情况下完成逆序操作需要Ω( n)时间，不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O( logn)，适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O( n0. 5 )，适用于大规模的旅行商问题。
Abstract:
 The data structure of tour for the traveling salesman problem plays a critical role in the efficiency of local heuristic algorithms. The data structure of tour must permit queries about the relative order of cities in the tour and must allow sections of the tour to be re-versed. The implementation and time complexity of several basic operations when the tour is represented by array,splay tree and two-lev-el tree are analyzed. The array-based representation of a tour permits the relative order of cities to be determined in small constant time, but requires worst-caseΩ( n) time to implement a reversal,which renders it impractical for large instances. For the data structure based on splay tree,all queries and updates take amortized time O( logn) ,which is available for extremely large-scale traveling salesman problem. For the data structure based on two-level tree representation,the worst-case time for each update operation is O( n0. 5 ) ,which is available for large-scale traveling salesman problem.

相似文献/References:

[1]段凤玲 李龙澍 曹文婷.具有多态特征和聚类处理的蚁群算法[J].计算机技术与发展,2009,(12):77.
　DUAN Feng-ling,LI Long-shu,CAO Wen-ting.Ant Colony Algorithm with Polymorphism and Clustering Processing[J].,2009,(12):77.
[2]杨益 方潜生 高翠云.求解TSP问题的遗传算法硬件实现[J].计算机技术与发展,2009,(04):54.
　YANG Yi,FANG Qian-sheng,GAO Cui-yun.Implementation of Hardware Based on Genetic Algorithm for Solving TSP Problem[J].,2009,(12):54.
[3]王娟 王建.一种求解TSP问题的改进蚁群算法[J].计算机技术与发展,2008,(12):50.
　WANG Juan,WANG Jian.An Improved Ant Colony Algorithm for Solving TSP Problem[J].,2008,(12):50.
[4]苏劲松 周昌乐 蒋旻隽.一种基于逆转算子的求解TSP问题的改进演化算法[J].计算机技术与发展,2007,(07):94.
　SU Jin-song,ZHOU Chang-le,JIANG Min-jun.An Improved Evolutionary Algorithm for Traveling Salesman Problem Based on Inver- Over Operator[J].,2007,(12):94.
[5]陈文兰 戴树贵.求解旅行商问题的混合蚂蚁算法[J].计算机技术与发展,2007,(07):110.
　CHEN Wen-lan,DAI Shu-gui.A Hybrid Ant Colony Algorithm for Solving Traveling Salesman Problem[J].,2007,(12):110.
[6]孙宪丽 王敏 李颖.求解TSP问题的一种启发式算法[J].计算机技术与发展,2010,(10):70.
　SUN Xian-li,WANG Min,LI Ying.A Heuristic Algorithm to Solve Travelling Salesman Problem[J].,2010,(12):70.
[7]赵玉章 郭文强 冯昊[].基于二点组合算法的旅行商问题应用性能分析[J].计算机技术与发展,2011,(10):137.
　ZHAO Yu-zhang,GUO Wen-qiang,FENG Hao.Performance Analysis of Two Vertices Combination Algorithm in TSP[J].,2011,(12):137.
[8]赵越,徐鑫,赵焱,等.自适应记忆遗传算法研究[J].计算机技术与发展,2014,24(02):63.
　ZHAO Yue[],XU Xin[],ZHAO Yan[],et al.Research on Adaptive Memory Genetic Algorithm[J].,2014,24(12):63.
[9]张志宏,吴庆波,邵立松,等.基于飞腾平台TOE协议栈的设计与实现[J].计算机技术与发展,2014,24(07):1.
　ZHANG Zhi-hong,WU Qing-bo,SHAO Li-song,et al. Design and Implementation of TCP/IP Offload Engine Protocol Stack Based on FT Platform[J].,2014,24(12):1.
[10]梁文快,李毅. 改进的基因表达算法对航班优化排序问题研究[J].计算机技术与发展,2014,24(07):5.
　LIANG Wen-kuai,LI Yi. Research on Optimization of Flight Scheduling Problem Based on Improved Gene Expression Algorithm[J].,2014,24(12):5.
[11]易正俊[],李勇霞[],易校石[].自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2016,26(12):1.
　YI Zheng-jun[],LI Yong-xia[],YI Xiao-shi[]. Solving of Shortest Path Problem and TSP with Adaptive Ant Colony Algorithm[J].,2016,26(12):1.

更新日期/Last Update: 2015-04-15