TSP问题：最坏情况比率增加

Question

作为我高中论文的一部分，我正在描述旅行商问题的启发式算法。我正在阅读 this 这种案例研究（第8页），但我不理解这些句子的意思:

NN的运行时间如上所述是Θ(N^2)。[...]特别地，我们保证 NN(I)/OPT(I) ≤ (0.5)(log_{2}N+1)。

对我来说，那部分非常清楚。但接下来是:

然而，没有更好的保证是可能的，因为有一些实例使得比率随着 Θ(logN) 的增长而增长。

“存在这样的实例”是什么意思？

贪心算法也是同样的情况：

...但已知的贪心算法最差的例子只能使比率增长为 (logN)/(3loglogN)。

那么这些语句的意思是什么？与非欧几里得实例有关吗（我认为不是，因为你只需要阅读距离矩阵的一列就可以解决它）？还是只是具有相同距离的多个节点的实例，需要算法将解决方案树分裂或类似的操作？

编辑：感谢@templatetypedef（您的答案仍将被接受为正确），这一切都说得通。但我想问一下，是否有人知道这些特定图形的任何示例（甚至只是一个链接）（无论使用哪种算法）。我认为这并不太离题，它会为话题增添一些有用的内容。

- Spinnaker

---

你的高中论文似乎比一些本科论文更为先进... +1 - user541686

存在一个常数c > 0，对于每个大于0的整数n，都存在一个包含n个点的TSP实例，使得（NN产生的旅行长度/最优旅行长度）> c log n。你可以将c精神上重写为0.000001（例如）。 - David Eisenstat

关于您的编辑：http://down.cenet.org.cn/upfile/47/20061030111839196.pdf - David Eisenstat

Answer 1

请看这两个语句的对比：

特别地，我们保证 NN(I)/OPT(I) ≤ ( 0. 5 ) ( log_{2} N + 1 )。

然而，对于某些实例，比率增长为 Θ( logN)，因此不可能有更好的保证。

第一条语句表示，在最坏情况下，算法NN得出的答案与真实答案相差不超过大约1/2 lg N（要想看到这一点，只需将两边乘以OPT(I)）。这是一个好消息！自然而然的后续问题是，实际上的界限是否更紧。例如，该结果并未排除NN(I) / OPT(I) ≤ log log N或NN(I) / OPT(I) ≤ 2的可能性。这些都是更紧密的界限。

那么第二个陈述就非常重要了。这个陈述说有已知的TSP实例（也就是具有权重的特定图形），其中NN(I) / OPT(I)的比率为Θ(log n)（也就是该比率与图中节点数量的对数成比例）。因为我们已经知道了这样的输入，所以NN(I) / OPT(I)不可能被类似于log log n或2之类的东西所限制，因为这些限制太紧了。

然而，仅靠第二个陈述是不太有用的。我们知道有些输入会导致算法产生与实际结果相差一个对数因子，但是否仍可能存在某些输入会导致它偏差更大，比如指数级别的偏差？有了第一个陈述，我们知道这是不可能的，因为我们知道我们永远不会超过一个对数因子的偏差。

这些语句可以分为两步：第一步给出了近似程度的上限，最坏情况下不会超过最优解的1/2 lg N + 1倍。第二步给出了近似程度的下限，某些特定情况下算法无法得到比最优解更好的Θ(log N)近似结果。

（注意，这里的Θ(log n)与运行时间无关，只是一种表示“对数”的方式。）

在接下来的研究中，请同时关注上限和下限。两者的综合信息比单独一项更加有价值。

祝论文顺利！

- templatetypedef