我有期末考试的复习，这个问题对我来说特别令人困惑。我需要一个关于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的任何解决方案都必须是哈密顿循环。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句