一种基于最大相似性的TSP问题求解算法

被引：13

作者：

邓娟

陈莘萌

机构：

[1] 武汉大学计算机科学学院

[2] 武汉大学计算机科学学院武汉

[3] 武汉

来源：

计算机工程 | 2004年 / 17期

关键词：

TSP问题; 最近邻算法; 最大相似性算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

提出了一种新的基于最大相似性的TSP问题求解算法。该算法在最近邻算法(Nearest-Neighbor Algorithm)的基础上作了改进,将最短路径问题转换为最大相似性问题,即将问题由选取城市 ij+1= arg min{djk:k ∈V\ {i1, i2,…,ij}} 转换为选取城市 ij+1= arg min{wjk:k ∈V\ {i1, i2,…,ij}} ,wjk 为城市i与城市j之间的相似系数。实验结果表明,该算法简明且具有较好的有效性。

引用

页码：1 / 2+11 +11

页数：3