python - Networkx 旅行商问题 (TSP)

Question

我想知道NetworkX中是否有解决TSP的功能？我找不到它了。我错过了什么吗？我知道这是一个 NP 难题，但应该有一些近似的解决方案吧？

标签： pythonnetworkxmathematical-optimization

Answer 1

Networkx 为 TSP 提供了一个近似的解决方案，请参阅第 页。他们的解决方案基于将 TSP 写为二次无约束二进制优化 (QUBO) 问题。

请注意，已证明找到 TSP 的 alpha 近似值通常被证明是 NP 难的。因此，您无法保证所获得结果的质量。但是有一个特殊情况，欧几里得-TSP，我们可以使用Christofides 算法构造 TSP 的 2 近似甚至 1.5 近似，但是我无法在 Networkx 中找到该算法的实现。