# 问题描述

$$L(S) = ( \sum_{i=0}^{n-2} d_{S_iS_{i+1}}) + d_{S_{n-1}S_{0}} \tag{1}$$

# 传统的贪心算法

(1) 添加该边后不会使任何点的连接边数量大于2；
(2) 该边也不会使图$G$产生边数小于$n$的圈。

# 改进思路

• 改进距离矩阵

$L’( S)$ 表示该解按改进后边长矩阵计算的路径总长度。

\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}

• 跳出局部最优

$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)$

# 实验结果

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