小编Spi*_*ker的帖子

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

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

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

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

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

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

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

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

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