作为我高中论文的一部分，我描述了旅行商问题的启发式方法。 我在读this某种案例研究(第 8 页)，但我无法理解这些句子的含义:
The running time for NN as described is Θ(N^2 ). [...] In particular, we are guaranteed that NN (I)/OPT (I) ≤ ( 0. 5 ) ( log_{2} N + 1 ).
这部分我很清楚。但是然后:
No substantially better guarantee is possible, however, as there are instances for which the ratio grows as Θ( logN).
there are instances for which是什么意思？
同样的事情发生在贪心算法上:
...but the worst examples known for Greedy only make the ratio grow as ( logN)/( 3 log log N).
那么这些语句的含义是什么？它是否与非欧几里得实例有关(我不这么认为，因为您只需阅读距离矩阵的列即可解决它)？或者只是实例与例如距离起始节点相同距离的多个节点需要算法来拆分解决方案树或类似的东西？
编辑: 感谢@templatetypedef(您的答案仍将被认为是正确的)，这一切都说得通。但是，我想问问是否有人知道这些特定图形 的任何示例(甚至只是一个链接)(我不关心哪种算法)。我不认为它太离题了，它宁愿添加一些对主题有用的东西。
最佳答案
并排查看这两个语句:
In particular, we are guaranteed that NN (I)/OPT (I) ≤ ( 0. 5 ) ( log_{2} N + 1 ).
No substantially better guarantee is possible, however, as there are instances for which the ratio grows as Θ( 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) 与运行时无关——它只是一种表达“某种对数”的方式。)
展望 future ，请留意上限和下限。这两者加在一起告诉您的信息比任何一个人单独告诉您的要多得多。
祝论文顺利!
关于algorithm - 茶匙 : Worst case ratio grows，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32102639/