旅行商问题基于参考点的相邻插入法及其改进

• 作者: 何京芮 王凌 童行行
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 旅行商问题 构造性算法 参考点 相邻插入法 多项式时间算法
• 年，卷（期）: 2002,（20）
• 所属期刊栏目: 学术探讨
• 页码范围: 63-65
• 页数: 3页
• 分类号: TP301.6
• 字数: 3577字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2002.20.021

摘要

旅行商问题(Traveling Salesman Problem,TSP)是典型的NP-hard问题.通过对已有以最近插入法为代表的构造性算法的分析,提出了一种具有多项式时间性能的基于参考点的相邻插入法及其改进策略,其时间复杂度分别为O(n2)和O(n3),同时基于典型算例的仿真研究验证所提出算法的有效性和高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王凌	清华大学自动化系	86	2991	29.0	53.0
2	童行行	清华大学自动化系	2	31	2.0	2.0
3	何京芮	清华大学自动化系	1	20	1.0	1.0