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

被引：7

作者：

童行行

王凌

何京芮

不详

机构：

[1] 清华大学自动化系

[2] 清华大学自动化系北京

[3] 北京

来源：

计算机工程与应用 | 2002年 / 20期

关键词：

旅行商问题; 构造性算法; 参考点; 相邻插入法; 多项式时间算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：63 / 65

页数：3

共 8 条

[1] 一种GASA混合优化策略 [J].