Travelling Sales Man problem

Question

I am studying the Travelling Sales Man problem:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

And I wonder: given a list of cities/distances that the salesman must visit, is it possible to estimate the solution (shortest path) without finding it? Or is doing a rough estimate about as hard as finding the actual paths?

score 0 · Accepted Answer · answered Mar 21 '15 at 17:12

0

There are, see here. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution.

answered Mar 21 '15 at 17:12

Pedro

983
1
6
19

Travelling Sales Man problem

1 Answers1