度量TSP的MST启发式紧例

Question

我正在寻找MST启发式的紧例子，这是度量旅行推销员问题的2-近似算法。

这种算法在互联网上很容易找到，但我找不到严密的例子。在严格的例子中，我指的是给出的算法返回比最优更差两倍的解的例子。

谢谢。

Answer 1

我能想到的最接近的例子就是这样。考虑一个有n个节点的恒星:1节点、中心节点和n-1节点.每个节点都以1的成本连接到中心。

现在把这颗星放入一个长度(n - 1)的循环中，其中每两个节点的连接成本为2。注意，周期中的节点是非中心节点。现在，MST将给成本n- 1和TSP约.使用MST将给出(n-2)*2+1

所以，当n变大时，近似的比值是(2n - 3) /(n-1)，它趋向于2(你想要的)。