旅行商问题中巡回路径的数据结构

• 作者: 宗德才 王康康
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 旅行商问题 局部启发式算法 数组 伸展树 两级树
• 年，卷（期）: 2014,（12）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 72-77
• 页数: 6页
• 分类号: TP311.12
• 字数: 4901字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2014.12.018

摘要

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序，并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序，但是最坏情况下完成逆序操作需要Ω( n)时间，不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O( logn)，适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O( n0. 5 )，适用于大规模的旅行商问题。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宗德才	常熟理工学院计算机科学与工程学院	26	116	5.0	10.0
2	王康康	江苏科技大学数理学院	52	217	8.0	11.0