我遇到了以下问题：
考虑以下启发式： 从仅包含一个顶点的游览开始。在每一步中，找到游览之外的顶点，与游览的某个顶点的距离较小。设 v 为外顶点， u 为内顶点。在游览中添加 v。假设您的边遵循三角形距离属性。我们如何证明这种启发式方法是 TSP 度量问题的 2 近似值？
有谁知道如何开始？
提前致谢
问问题
482 次
1 回答
1
显然，无法证明所描述的算法不是2 近似值。维基百科文章提到了该出版物
罗森克兰茨，丹尼尔 J.；斯特恩斯，理查德 E.；Lewis, Philip M., II (1977)，“旅行商问题的几种启发式分析”，SIAM Journal on Computing 6 (5): 563–581, doi:10.1137/0206041
其中作者显然表明，最近邻启发式产生的近似比为Theta( log n )，其中n是位置的数量，即使实例满足三角不等式：
罗森克兰茨等人。[1977] 表明，对于满足三角不等式的实例，NN 算法具有近似因子 Theta(log|V|)。
但是，OP 可能已经描述了不同的算法；不同贪心启发式算法的逼近比分析可以在下面的文章中找到。
SIAM 计算杂志，1977 年，卷。6, No. 3 : pp. 563-581 旅行推销员问题的几种启发式分析 Rosenkrantz, D., Stearns, R. 和 Lewis, II, P. (doi: 10.1137/0206041)
于 2014-06-16T14:47:01.040 回答