换前后的路径增益，用

Yb 段替代 Xa 段产生的增益 ，如果 Z=Z1+Z2+Z3+

……+Zk≥0，就

显示交换之后的总路径比交换之前的总路径要小，即此次

 k 元交换有效，如此往复最后得

到的将是这个算法下的最优解。这里需要注意的是选择

Ya 的限定条件：为了简化编程和减

少计算量，限定

Ya 只在距离 T2a 的最近五个点之中寻找 T2a+1。 

　　

2.2 最近邻算法 

　　最近邻算法又被称为贪婪算法。它的思想是每次移动前都寻找离当前所在点最近的点作
为目的地。具体步骤如下：

 

　　第一步，从任意点

a1=1，2，3，

……，n 出发寻找与出发点最近的点 a2；第二部，把

a2 作为起点重复第一步操作，直到回到 a1。 
　　对于

 n 点的路径，这种算法得到的解基一般会超出最优解 25%。特别需要注意的是，对

于某些情况下，最近邻算法得到的解可能会是个很差的结果。

 

　　

3. 结语 

　　

K 元交换试探算法的步骤和编程实现均比较繁杂、计算量较大；而最近邻算法的特点在

于步骤简单、编程较为容易、且计算量较小。可以看到在点的个数比较小的情况下，两种算法
得到了同样的最优解，这时可以采取最近邻算法。但是当点的个数增加到一定数目时，

K 元

交换试探算法更具优势，它的解比最近邻算法得到的解更优，这时应当采取

K 元交换试探

算法。

 

　　参考文献

 

　　

[1] Johnson DS，McGeoch LA. The Traveling Salesman Problem： A Case Study in Local 

Optimization. Local Search in Combinatorial Optimization. Chichester；New York： John Wiley 
and Sons，1997，：215-310. 
　 　

[2]  Keld  Helsgaun. 

“An  Effective  Implementation  of  K-opt  Moves  for  the  Lin-Kernighan 

TSP Heuristic

”. Writings on Computer Science. Roskilde University，2007，Vol.109：225-226.