基于分段多方位近邻算法求解TSP问题

被引：1

作者：

向佐勇 ^{[1
]}

陈端来 ^{[2
]}

机构：

[1] 中南林业科技大学理学院

[2] 湖南科技大学数学与计算机学院

来源：

湖南科技大学学报(自然科学版) | 2009年 / 24卷 / 04期

基金：

湖南省自然科学基金;

关键词：

TSP; 环路构造法; 角点; 最近邻搜索法; 方位近邻;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

在利用构造法求解欧氏平面上的TSP问题时,先构造1个只包含4个结点(左上角结点-右上角结点-右下角结点-左下角结点-左上角结点)的简单的环路,这个环路将求解路径分成4段.每个序列每一步都是从当前结点出发,在4个方位近邻结点中按照距离与方位的因素综合考虑选择一个较为合理的近邻结点作为下一步的目标结点,直至每个序列都到达其终点,然后将剩余的结点加入其中的某个序列,最后将4个序列首尾相接形成环路.实验表明,它将经典的最近邻算法的求解结果的精度提高了一个数量级,在许多例子中NN求解长度是它的2～28倍,它的长解长度与最优解的比小于2.8,总体上来说它的性能与最近插入法的性能相当接近.图8,表1,参6.

引用

页码：79 / 84

页数：6