引言

不知道为什么，可能我对TSP问题有一种执念吧，所以在这次计算机算法设计与实践的课程设计中我还是毅然选择了TSP问题。

关于TSP问题的算法概述详见我的上一篇博客：TSP问题

在本篇博客中我将结合算法课上的贪心算法、近似算法、概率算法的思想，考虑基于求解TSP问题的传统的贪心算法的改进。

问题描述

一个 TSP 问题的解( 路径) 可表示为 $n$ 个城市${ 1，2，…，n}$ 的环状排列。
令 $S$ 为存放了一个解的一维数组，那么此解的旅行总距离( 路径总长度) 可由公式$(1)$ 计算:
$$
L(S) = ( \sum_{i=0}^{n-2} d_{S_iS_{i+1}}) + d_{S_{n-1}S_{0}} \tag{1}
$$
显然，使得$L(S)$ 取得最小值的一维数组$S$中存放的排列为TSP问题的最优解。

传统的贪心算法

传统的贪心算法的求解原理是根据距离矩阵中 $D$ 的距离( 边长) 信息，按照从小到大排列，从最短边开始依次添加可以添加的边至图 $G$ 中，直到添加完 $n$ 条边形成一个简单圈为止。
显然，该算法的复杂度为 $O( n^2 \log n)$.
而判断一条边是否为可添加边的准则是:
(1) 添加该边后不会使任何点的连接边数量大于2；
(2) 该边也不会使图$G$产生边数小于$n$的圈。
这是一种典型的局部最优的思路，这时发现影响算法求解质量的主要因素是在构造后期添加的边过长，从而导致最终求解质量不高。

例如，我们来看一篇论文的研究结果，求解城市数量为 130 的算例 ch130 的过程示意图如图所示。

由图可知，传统的贪心算法求解算例 ch130 在最后添加的边非常长，如$( c)$ 子图到$( d)$ 子图添加的最后 $13$ 条边均为较长的边，经计算这 $13$ 条边的总长度占总路径长度的 $42. 01%$ ，这是最终解质量不高的主要原因。
经过进一步分析可得用传统的贪心算法求解其他算例时与算例 ch130 具有相同的规律，在以下表格中列出了求解的 48 个算例( 均来自 TSPLIB 标准算例库)的路径中最长的$ \lfloor n/10\rfloor$ 条边的长度和占总路径长度的百分比数据。

由表可知，传统的贪心算法求解所有的算例均有在最后阶段连接的较长边的缺点。
因此，如果采取有效措施提高在最后阶段的求解质量，会明显提高算法的总体求解质量。

改进思路

因此，基于上述原因，我主要想从改进距离矩阵和跳出局部最优搜索两个方面改进传统的贪心算法。

改进距离矩阵

基本思路是先找到一个中心点，可由所有城市的平均中心位置得到,创建这个新的中心城市，然后将所有城市与中心城市的距离重新排序得到一个新的距离矩阵。
此时假设新距离矩阵相比原距离矩阵改变的路径长度为$\delta$，
设 $L( S)$ 表示该解按原边长矩阵计算的路径总长度，
$L’( S)$ 表示该解按改进后边长矩阵计算的路径总长度。
因 TSP 问题的解是 $n$ 个点( 城市) 标号的环状排列，
在解( 路径) 中每个点均连接两条边，据公式$( 1)$ 可得 $L’( S)$ 的计算式，如式$(2)$ 所示。

$$
\begin{aligned} L^{\prime}(S) &=\left(\sum_{i=0}^{n-2} d_{S, S_{i+1}}^{\prime}\right)+d_{S_{n-1} S_{0}}^{\prime} \ &=\left(\sum_{i=0}^{n-2} d_{S_{i} S_{i+1}}-\delta\right)+\left(d_{S_{n-1} S_{0}}-\delta\right) \ &=\left(\sum_{i=0}^{n-2} d_{S_{i} S_{i+1}}\right)+d_{S_{n-1} S_{0}}-2 \delta \ &=L(S)-2 \delta \end{aligned}
\tag{2}
$$

由式$(2)$ 易见，对于一确定的$\delta$，任何解 $S$ 对应的 $L(S)$ 与 $L’(S)$ 之差为常数。
显然，将解空间中每个解的路径长度都增加或减少相同的值不会影响解之间的路径长度比较，
由此可知改进前后的边长矩阵具有同样的近似最优解。

跳出局部最优

在改进距离矩阵的基础上，得到一个初步的改进了传统的贪心算法的一条近似最优路径，在这条路径上利用2-opt算法加以优化，2-opt算法即为：随机选取两点i和k，将i之前的路径不变添加到新路径中，将i到k之间的路径翻转其编号后添加到新路径中，将k之后的路径不变添加到新路径中。例如：
原路径:
$A ==> B ==> C ==> D ==> E ==> F ==>G ==> H ==> A$
$i = 4, k =7$
新路径:
$1. \quad(A ==> B ==>C)$
$2. \quad A ==> B ==> C==> (G ==> F ==> E ==> D)$
$3. \quad A ==> B ==> C==> G ==> F ==>E==> D(==>H==> A)$
从而获得一个新的可行解。
将可行解代入目标函数可得目标函数值，将其与$S_{min}$的目标函数值比较，取两者目标函数值较小的可行解为$S_{min}$，直到找不到比$S_{min}$还小的函数值为止。
同时，为了防止陷入局部最优解，在此基础之上，我利用模拟退火算法，模拟退火算法即为：从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即以一定的概率跳出局部最优并最终趋于全局最优。

实验设置

考虑到在TSP问题中找到一个最坏解和一个最优解其实难度是一样的，所以我选择通过概率算法得到一条随机路径作为算法最终效果对比的上界，然后分别通过比较这五种算法在三大国际tsplib网站上提供的数据集进行测试，对比分析近似最优解的质量和得到解的时间。

实验结果如下图所示。

实验结果

lenth	random	greedy	optimize	2-opt	SA
p15	41383	24628	23927	20348	20348
att48	157530	40526	38755	34405	34010
cities200	327452	36226	36260	31861	30458

time	random	greedy	optimize	2-opt	SA
p15	6.09s	5.89s	5.93s	5.47s	121.25s
att48	9.04s	8.62s	8.81s	5.80s	133.21s
cities200	25.90s	23.52s	23.89s	11.40s	488.88s

五种算法的时间消耗量比较

四种算法的时间消耗量比较

五种算法的最短路径比较

参考文献
An Empirical Analysis of Approximation Algorithms for the Euclidean Traveling Salesman Problem

基于求解 TSP 问题的改进贪婪算法