0
$\begingroup$

It's well known that to find a hamilton cycle is NPC, while TSP is NPH.

But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different hamilton cycles if the graph is hamilton graph. For example, g = graphs.RandomGNP(1300,0.1), it takes 31453 seconds to find 100000 different solutions by SageMath.

Thus there is a possibility to get a solution of TSP within reasonable time.

In order to know the level of possibility, could you provide some TSP examples (answer is known but not let me know in advance) from real world?

$\endgroup$

1 Answer 1

2
$\begingroup$

Bill Cook's page provides lots of real-world TSP instances of various sizes: http://www.math.uwaterloo.ca/tsp/data/index.html

Cook is one of the developers of the state-of-the-art TSP solver Concorde.

See also TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

$\endgroup$
1
  • $\begingroup$ Thanks! I will test them. $\endgroup$ May 1, 2021 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.