| 旅行商问题中巡回路径的数据结构 |
| |
| 引用本文： | 宗德才,;王康康.旅行商问题中巡回路径的数据结构[J].微机发展,2014(12):72-77. |
| |
| 作者姓名： | 宗德才 ;王康康 |
| |
| 作者单位： | [1]常熟理工学院计算机科学与工程学院,江苏常熟215500; [2]江苏科技大学数理学院,江苏镇江212003 |
| |
| 基金项目： | 江苏省高校自然科学基础研究项目（13KJB110006）; 常熟理工学院青年教师基金项目（CST201209） |
| |
| 摘 要： | 旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。
|
| 关 键 词： | 旅行商问题 局部启发式算法 数组 伸展树 两级树 |
Data Structure of Tour for Traveling Salesman Problem |
| |
| Affiliation: | ZONG De-cai ,WANG Kang-kang ( 1. College of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500 ,China; 2. School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang 212003, China) |
| |
| 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 allowsections of the tour to be reversed. The implementation and time complexity of several basic operations when the tour is represented by array,splay tree and two-level 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（ log n）,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. |
| |
| Keywords: | traveling salesman problem local heuristic algorithm array splay tree two-level tree |
| 本文献已被 维普 等数据库收录！ |
|
