Networkx Traveling Salesman Problem (TSP)

Networkx Traveling Salesman Problem (TSP)

2024/10/12 6:24:23

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?

Answer

Networkx provides an approximate solution to TSP, see page. Their solution is based on writting TSP as Quadratic Unconstrained Binary Optimization (QUBO) problem.

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.

https://en.xdnf.cn/q/69684.html

Related Q&A

Comparing dateutil.relativedelta

Im trying to do a > comparison between two relativedeltas: if(relativedelta(current_date, last_activity_date) > relativedelta(minutes=15)):Here is the output from the debugger window in Eclipse:O…

Python. Argparser. Removing not-needed arguments

I am parsing some command-line arguments, and most of them need to be passed to a method, but not all.parser = argparse.ArgumentParser() parser.add_argument("-d", "--dir", help = &q…

Where can I find some hello world-simple Beautiful Soup examples?

Id like to do a very simple replacement using Beautiful Soup. Lets say I want to visit all A tags in a page and append "?foo" to their href. Can someone post or link to an example of how to …

Difference between isnumeric and isdecimal in Python

What is the difference between isnumeric and isdecimal functions for strings ( https://www.tutorialspoint.com/python3/python_strings.htm )? They seem to give identical results: >>> "1234…

Estimating zip size/creation time

I need to create ZIP archives on demand, using either Python zipfile module or unix command line utilities. Resources to be zipped are often > 1GB and not necessarily compression-friendly.How do I e…

How to rename the index of a Dask Dataframe

How would I go about renaming the index on a dask dataframe? I tried it like sodf.index.name = foobut rechecking df.index.name shows it still being whatever it was previously.

Determine if a line segment intersects a polygon

If I have a vector (a line consisting of 2 points) on a 2D plane how can I determine if it has passed through a polygon? I know I can take each line which makes up the polygon and see if any intersect…

How to send a value from Arduino to Python and then use that value

I am in the process of building a robot that is remote controlled using Python to send control messages via the Internet through a simple GUI.I have gotten part of my code working pretty well, the GUI …

recaptcha wasnt solving by anticaptcha plugin in selenium python

Ive recently started using selenium for a project Ive been working on for a while that involves automation. One of the roadblocks in the plan was the ReCaptcha system, so I decided to use anti-captcha …

Python - check for class existance

Is there a way to check if a class has been defined/exists? I have different options on a menu, and some of them require inherited variables, so if you try to select that function before you have set …

Latest Q&A