问题描述
我想知道NetworkX中是否有解决TSP的功能?我找不到它了.我想念什么吗?我知道这是一个NP难题，但应该有一些近似的解决方案对吗?
I would like to know if there is a function in NetworkX to solve the TSP? I can not find it. Am I missing something? I know it's an NP hard problem but there should be some approximate solutions right?
推荐答案
Networkx提供了TSP的近似解决方案，请参见页面.他们的解决方案基于将TSP编写为二次无约束二进制优化(QUBO)问题.
Networkx provides an approximate solution to TSP, see page. Their solution is based on writting TSP as Quadratic Unconstrained Binary Optimization (QUBO) problem.
请注意，事实证明，找到与TSP的alpha近似值通常被证明是NP难的.因此，您无法保证所获得结果的质量.但是，在特殊情况下，欧几里得-TSP，我们可以使用 Christofides算法，但是我无法在Networkx中找到该算法的实现.
Note that it is proven that finding an alpha-approximation to TSP is proven to be NP-hard in general. So you can't have a guarantee on the quality the obtained result. Howver there is a particular case, Euclidean-TSP, where we can construct 2-approximation and even 1.5-approximation of TSP, using Christofides algorithm however I was not able to find the implementation of this algorithm in Networkx.
这篇关于Networkx旅行商问题(TSP)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！