TSP：最坏情况比率增长
TSP: Worst case ratio grows
作为我高中论文的一部分，我描述了旅行商问题的启发式方法。
我正在阅读 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).
有的实例是什么意思？
同样的事情发生在贪心算法上：
...but the worst
examples known for Greedy only make the ratio grow as ( logN)/( 3 log log N).
那么这些语句的含义是什么？它是否与非欧几里得实例有关（我不这么认为，因为您只需阅读距离矩阵的列即可解决它）？或者只是实例与例如距离起始节点相同距离的多个节点需要算法来拆分解决方案树或类似的东西？
编辑：
感谢@templatetypedef（您的答案仍将被认为是正确的），这一切都说得通。但是，我想问问是否有人知道这些 特定图表 的任何示例（甚至只是 link）（我不关心哪种算法）。不觉得太跑题了，倒是想给题主加点有用的东西。
并排查看这两个语句：
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) 与运行时无关 - 它只是 "something logarithmic." 的一种表达方式）
展望未来，同时关注上限和下限。这两者加起来告诉你的比任何一个人单独告诉你的都多。
祝论文顺利！
作为我高中论文的一部分，我描述了旅行商问题的启发式方法。 我正在阅读 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).
有的实例是什么意思？
同样的事情发生在贪心算法上：
...but the worst examples known for Greedy only make the ratio grow as ( logN)/( 3 log log N).
那么这些语句的含义是什么？它是否与非欧几里得实例有关（我不这么认为，因为您只需阅读距离矩阵的列即可解决它）？或者只是实例与例如距离起始节点相同距离的多个节点需要算法来拆分解决方案树或类似的东西？
编辑： 感谢@templatetypedef（您的答案仍将被认为是正确的），这一切都说得通。但是，我想问问是否有人知道这些 特定图表 的任何示例（甚至只是 link）（我不关心哪种算法）。不觉得太跑题了，倒是想给题主加点有用的东西。
并排查看这两个语句：
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) 与运行时无关 - 它只是 "something logarithmic." 的一种表达方式）
展望未来，同时关注上限和下限。这两者加起来告诉你的比任何一个人单独告诉你的都多。
祝论文顺利！