| 基于分段多方位近邻算法求解TSP问题 |
| |
| 引用本文： | 向佐勇,陈端来.基于分段多方位近邻算法求解TSP问题[J].湖南科技大学学报(自然科学版),2009,24(4). |
| |
| 作者姓名： | 向佐勇 陈端来 |
| |
| 作者单位： | 1. 中南林业科技大学,理学院,湖南,长沙,410004
2. 湖南科技大学,数学与计算机学院,湖南,湘潭,411105 |
| |
| 基金项目： | 湖南省自然科学基金资助项目，中南林业科技大学青年基金资助项目 |
| |
| 摘 要： | 在利用构造法求解欧氏平面上的TSP问题时,先构造1个只包含4个结点(左上角结点-右上角结点-右下角结点-左下角结点-左上角结点)的简单的环路,这个环路将求解路径分成4段.每个序列每一步都是从当前结点出发,在4个方位近邻结点中按照距离与方位的因素综合考虑选择一个较为合理的近邻结点作为下一步的目标结点,直至每个序列都到达其终点,然后将剩余的结点加入其中的某个序列,最后将4个序列首尾相接形成环路.实验表明,它将经典的最近邻算法的求解结果的精度提高了一个数量级,在许多例子中NN求解长度是它的2～28倍,它的长解长度与最优解的比小于2.8,总体上来说它的性能与最近插入法的性能相当接近.
|
| 关 键 词： | 环路构造法 角点 最近邻搜索法 方位近邻 |
Multi segment and multi orientation nearst neighbor solving TSP |
| |
| XIANG Zuo-yong,CHEN Duan-lai.Multi segment and multi orientation nearst neighbor solving TSP[J].Journal of Hunan University of Science & Technology(Natural Science Editon),2009,24(4). |
| |
| Authors: | XIANG Zuo-yong CHEN Duan-lai |
| |
| Abstract: | |
| |
| Keywords: | TSP |
| 本文献已被 万方数据 等数据库收录！ |
|
