algorithm - 使用 MST 为 TSP 找到最有效的上限

Question

我很好奇什么最有效的方法是使用 MST 找到 TSP 的最佳（或接近最佳）上限。我正在尝试优化我的算法以提高速度，但是在找到 MST 后，我在算法上计算“好”边界时遇到了麻烦。我知道一个基本界限是2 x MST length，但这似乎不是我们能做的最好的。任何参考或见解将不胜感激。

Answer 1

您可能应该将 MST 转换为游览，这将在线性时间内为您提供小于 2 * MST 长度的界限。MST 还有一个扩展，称为 Christofide 算法，可能也值得研究。

建议查看TSP heuristics的 Wikipedia 页面。