TSP:最差案例比率增长

Question

作为高中毕业论文的一部分,我正在描述旅行推销员问题的启发式方法.我正在阅读这种案例研究(第8页),但我无法理解这些句子的含义:

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

那部分对我来说很清楚.但是之后:

然而,没有实质上更好的保证是可能的,因为存在比率增长为Θ(logN)的情况.

有什么实例的含义是什么？

贪心算法也会发生同样的事情:

...但是Greedy最着名的例子只会使比率增长为(logN)/(3 log log N).

那些陈述的含义是什么？它是否与非欧几里德实例有关(我不这么认为,因为你只需要通读距离矩阵的列来解决它)？或者只是具有例如与起始节点相同距离的多个节点的实例,这些节点需要算法来拆分解决方案树或类似的东西？

编辑: 感谢@templatetypedef(您的答案仍将被接受为正确),这一切都是有道理的.但是,我想问一下是否有人知道这些特定图形的任何示例(甚至只是一个链接)(我与哪种算法无关).我不认为它太偏离主题,它宁愿添加对该主题有用的东西.

Answer 1

并排看一下这两个声明：

\n\n

\n

特别是，我们保证 NN (I)/OPT (I) \xe2\x89\xa4 ( 0. 5 ) ( log_{2} N + 1 )。

\n\n

然而，不可能有更好的保证，因为在某些情况下，比率会增长为 \xce\x98( logN)。

\n

\n\n

第一条语句表示，在最坏的情况下，算法 NN 生成的答案（大致）在真实答案的 1/2 lg N 范围内（要看到这一点，只需将两边乘以 OPT(I)）。这真是个好消息！那么，自然的后续问题是实际界限是否比这个更严格。例如，该结果并不排除我们也可能有 NN(I) / OPT(I) ≤ log log N 或 NN(I) / OPT(I) ≤ 2 的可能性。这些是更严格的界限。

\n\n

这就是第二个语句的用武之地。该语句表示存在已知的 TSP 实例（即带有权重的特定图），其中比率 NN(I) / OPT(I) 为 θ(log n) （也就是说，该比率与图中节点数的对数成正比）。因为我们已经知道这样的输入，所以 NN(I) / OPT(I) 不可能从上面被 log log n 或 2 之类的东西限制，因为这些限制太紧了。

\n\n

然而，单独的第二个陈述并不是很有用。我们知道有些输入会导致算法产生一些与对数因子偏差的东西，但仍然有可能存在一些输入导致算法偏差更大；比如说，按指数因子？通过第一个语句，我们知道这不会发生，因为我们知道我们永远不会得到超过对数因子的结果。

\n\n

分两步思考这些陈述：第一个陈述给出了近似值可能有多差的上限- 它永远不会比最佳的 1/2 lg N + 1 因子更差。在第二个语句中，给出了近似值的下限- 在某些特定情况下，算法不能比最佳答案的 θ(log N) 近似值更好。

\n\n

（请注意，这里的 θ(log n) 与运行时无关 - 它只是表达“对数”的一种方式。）

\n\n

展望未来，请留意上限和下限。两者共同告诉你的信息比任何一个单独告诉你的信息都要多。

\n\n

祝论文顺利！

\n