algorithm - 度量 TSP 的 MST 启发式的严格示例

Question

我正在寻找 MST 启发式算法的严格示例，它是度量旅行商问题的 2 近似算法。

这个算法在网上很容易找到，但我找不到具体的例子。我所说的严格示例是指给定算法返回的解决方案比最佳解决方案差 2 倍的示例。

谢谢。

Answer 1

我能想到的最接近的例子是这样的。考虑一个有 n 个节点的星:1 个节点在中心，n - 1 个节点围绕它。每个节点都以成本 1 连接到中心。

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

因此，近似值的比率是 (2n - 3)/(n - 1)，随着 n 变大，它趋向于 2(你想要的)。