表明旅行商 (TSP) 的 2 倍最优近似算法无法计算出最优解
Show that 2 times optimal approximation algorithm for traveling salesman (TSP) does not compute an optimal solution
我要复习期末考试，这个问题让我特别困惑。我需要一个关于 3 个顶点的示例，如果三角不等式的成本不成立，则旅行商问题 (TSP) 的 2 倍最优近似算法不会计算 2 倍最优解。
我尝试了一个三角形的示例，其成本为边 1、1 和 10。但是，要获得哈密顿循环，无论如何都必须遍历所有三个边。那么最优解将与该算法的近似解没有什么不同。我看这一切都错了吗？如果对此有任何帮助，我将不胜感激。
如果您有顶点 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的任何解一定是哈密顿环。
我要复习期末考试，这个问题让我特别困惑。我需要一个关于 3 个顶点的示例，如果三角不等式的成本不成立，则旅行商问题 (TSP) 的 2 倍最优近似算法不会计算 2 倍最优解。 我尝试了一个三角形的示例，其成本为边 1、1 和 10。但是，要获得哈密顿循环，无论如何都必须遍历所有三个边。那么最优解将与该算法的近似解没有什么不同。我看这一切都错了吗？如果对此有任何帮助，我将不胜感激。
如果您有顶点 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的任何解一定是哈密顿环。