摘要
旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω(n)时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O(logn),适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O(n0.5),适用于大规模的旅行商问题。
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.
出处
《计算机技术与发展》
2014年第12期72-77,共6页
Computer Technology and Development
基金
江苏省高校自然科学基础研究项目(13KJB110006)
常熟理工学院青年教师基金项目(CST201209)
关键词
旅行商问题
局部启发式算法
数组
伸展树
两级树
traveling salesman problem
local heuristic algorithm
array
splay tree
two-level tree
