algorithm - TSP 启发式 - 最坏情况比率

Question

我在尝试总结这些启发式算法的最坏情况比率时遇到了一些麻烦(这意味着它满足三角不等式)旅行商问题:

• 最近的邻居
• 最近的插入
• 最便宜的插入
• 最远插入

最近的邻居:

Here它表示 NN 的 w-C 比率为

This one ，第 8 页，同 this one说是

变化很大。

插入算法: 非常匹配，每个人都同意最便宜和最近插入的 w-c 比率 <= 2(总是只是为了满足三角不等式的实例)但是每个来源的最远插入都是不同的:

here :

(忘了把 NN 改成 FI)

同时 here 这是

和here还有一个不同的:

关于FI，我觉得还是要看首发的子游。 但在 NN 中，ceil 或 floor 括号对结果有很大影响，而且由于它们都来自良好的来源，我无法找出正确的那个。

有人可以总结出这些算法实际已知的最坏情况比率吗？

Answer 1

NN:正确的界限使用上限，而不是下限(至少如 Rosenkrantz 等人在原始论文中所证明的那样。-- here，如果您有权访问)。我认为最近没有使用 floor 的界限。

FI:Rosenkrantz 等人。证明第一个边界适用于任何插入启发式算法，包括 NN。此外，该界限优于其他两个界限(除了非常小的 n)。所以我会使用那个绑定(bind)。但是请注意，log 在该公式中实际上意味着 log_2。 (我不确定其他两个边界是从哪里来的。)

另一个注意事项:众所周知，神经网络没有固定最坏情况界限。 不知道是否存在 FI 的固定最坏情况界限。