我在总结这些启发式方法对于度量（这意味着它满足三角形不等式）旅行商问题的最坏情况比率时遇到了一些困难：
最近的邻居
最近插入
最便宜的插入
最远插入
最近的邻居：
Here它说NN的w-C比为
This one，第8页，与this one所说的相同
变化很大。
插入算法：
每个人都同意最便宜和最近插入的w-c比here：（忘记将nn改为fi）
而here
它是
还有一个不同的原因：
here
关于FI，我认为这取决于开始的次巡演。
但是在nn中，ceil或floor支架改变了很多结果，因为它们都来自好的来源，所以我无法找出正确的来源。
有人能总结一下这些算法的实际已知最坏情况比率吗？
最佳答案
nn：正确的边界使用天花板，而不是地板（至少在rosenkrantz等人的原始论文中证明了这一点）。--here，如果您有访问权限）我不认为最近有一个用地板装订的。
FI:Rosenkrantz等人证明第一界适用于任何插入启发式，包括nn。而且，这个界比另外两个好（除了很小的n）。所以我会用那个装订不过，请注意，在这个公式中log实际上意味着log_2（我不确定其他两个边界是从哪里来的。）
另一个注意事项：已知NN没有固定的最坏情况界不知道FI是否有固定的最坏情况界限。
关于algorithm - TSP启发式-最坏情况比率，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32317208/