Networkx旅行商问题(TSP) [英] Networkx Traveling Salesman Problem (TSP)

问题描述

我想知道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的近似解决方案，请参见

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，我们可以使用

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)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！