algorithm - 表明旅行商 (TSP) 的 2 倍最优近似算法无法计算出最优解

Question

我有期末考试的复习，​​这个问题让我特别困惑。我需要一个关于 3 个顶点的示例，如果三角不等式的成本不成立，则旅行商问题 (TSP) 的 2 倍最优近似算法不会计算 2 倍最优解。 我尝试了一个三角形的示例，其成本为边 1、1 和 10。但是，要获得哈密顿循环，无论如何都必须遍历所有三个边。那么最优解将与该算法的近似解没有什么不同。我看这一切都错了吗？我将不胜感激。

Answer 1

如果您有顶点 A、B、C，边成本为 wAB、wAC 和 wBC，并假设三角不等式不成立。比如 wBC > wAB + wAC。

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

  A
 / \
B   C

从近似算法得到的解是这棵树的前序枚举(返回A)，即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 的任何解都必须是哈密顿循环。