Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
复制标题
DOI：
10.1007/s00453-013-9801-4
复制
发表时间：
2007-01
期刊：
影响因子：
1.1
通讯作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking
中科院分区：
文献类型：
--
作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking
2-OPT可能是TSP最基本的局部搜索启发式算法。这种启发式算法在“真实世界”欧几里得实例上获得了令人惊讶的良好结果，无论是在运行时间上还是在逼近比上。对2-OPT的性能进行了大量的实验研究。然而，关于这种启发式算法的理论知识仍然非常有限。到目前为止，它在2维欧几里得实例上的最坏情况运行时间也是未知的。我们通过给出一个2-opt可以采取指数步数的Lp实例族来阐明这个问题，以前的概率分析仅限于其中的点在单位平方[0，1]2中均匀随机放置的实例，其中证明了期望步数对于欧氏实例是有界的。我们考虑了一个更高级的概率实例模型，其中的点可以根据[0，1]d上的一般分布独立放置，对于任意d的≥2。特别地，我们允许不同的点有不同的分布。我们用概率分布的点数和最大密度ϕ来研究局部改善的预期数目。我们给出了的任意2-opt改进路径的期望长度的上界。当从由插入启发式计算的初始行程开始时，预期步数的上限甚至提高到。如果按照曼哈顿公制来测量距离，那么预期的步数是有界的。此外，我们还证明了关于所有Lp参数的期望逼近因子的上界为$O(\Sqrt[d]{\Phi})$。值得注意的是，作为特例，我们的概率分析涵盖了ϕ=1的均匀输入模型和标准差σ具有ϕ∼1/σd的高斯扰动的光滑分析。
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every, a family ofLpinstances on which 2-Opt can take an exponential number of steps.Previous probabilistic analyses were restricted to instances in whichnpoints are placed uniformly at random in the unit square [0,1]2, where it was shown that the expected number of steps is bounded byfor Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1]d, for an arbitraryd≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the numbernof points and the maximal densityϕof the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of. When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to. If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by. In addition, we prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation factor with respect to allLpmetrics.Let us remark that our probabilistic analysis covers as special cases the uniform input model withϕ=1 and a smoothed analysis with Gaussian perturbations of standard deviationσwithϕ∼1/σd.