证明了旅行商的2倍最优逼近算法并不能计算出最优解。

Question

我有期末考试的复习，这道题让我特别困惑。本文给出了一个关于旅行商问题(TSP)的2倍最优逼近算法在三角不等式不成立的情况下不计算2倍最优解的例子。我试过一个三角形的例子，它的代价是1，1，10。然而，要得到哈密顿循环，所有三条边都要经过。这样，最优解将与此算法的近似解没有什么不同。我看错了吗？我希望能在这方面提供任何帮助。

Answer 1

如果有顶点A，B，C，边代价为wAB，wAC和wBC，并且假定三角形不等式不成立。比如wBC > wAB + wAC。

然后，假设我们从A开始，近似算法将找到根A的最小生成树，这是：

  A
 / \
B   C

近似算法的解是A->B->C->A -的树的预序枚举，它的总权重为wAB + wBC + wCA。A->B->A->C->A -> wAB + wAC + (wAB + wAC) < wAB + wAC + wBC = wAB + wBC + wCA。这里的<步骤使用了关于三角形不等式不成立的原始假设。

通过选取足够大的wBC，我们可以使近似任意差(例如，差于最优2倍)。例如，在权重为1、1、10的情况下，最优路径的总成本为4，但近似算法为12。

在你的想法中的错误是，当看到近似算法产生一个哈密顿循环时，推断出TSP的任何解都必须是哈密顿循环。