Traveling Salesman Problem

A salesman needs to visit each city in a list of cities and return to his home base. He knows the distance between each pair of cities, and wishes to minimize the total distance he is to travel. What should his path be?

This is an NpComplete problem. If there are n cities, exhaustive search would require (n-1)! trials, and no better method for finding the guaranteed-optimal solution in the worst case is known (nor possible, except in the unlikely event that someone manages to prove that P=NP), but there are many algorithms that are better in many non-worst-case situations.

It's not true that there's no better method than trying every single possibility, even if you insist on guaranteeing that you have the optimal solution. BranchAndBound techniques can help considerably, especially on easier instances. What is true is that there's no way of getting an optimal solution that isn't appallingly slow in the worst case for large problems.


This is similar to the Towers of Hanoi with more than three poles. There are several sites dedicated to this phun piece of math; they'll be posted later.

See "Exponential Lower Bounds for the Towers of Hanoi with More Than Three Pegs", 1998, Mario Szegedy http://citeseer.ist.psu.edu/szegedy98exponential.html


Okay, so someone straighten me, cause I'm bent:

I'm doing something silly. Help me and point it out. --PeterMerel

For example (check page source to correct formatting due to the WikiBackslashBug...):

 a - 2 - b
  \     / \ 
   1   4   3
    \ /     \ 
     c - 2 - d
gives the weighted connectivity matrix M1:

    a      b      c      d
 a  *      2      1      *
 b  2      *      4      3
 c  1      4      *      2
 d  *      3      2      *
M2:

    a      b      c      d

a * 5(acb) 6(abc) 3(acd) b 5 * 3(bac) 6(bcd) c 6 3 * 7(cbd) d 3 3 7 *
M3:

   a      b       c      d
 a *      6(acdb) *      8(abcd)
 b 6      *       *      5(bacd)
 c *      *       *      6(cabd)
 d 8      5       6      *
And the TSP here is bacd, length 5, in a bit less than N^3 trials. Or dcab, natch. Each matrix is just generated from the previous one by adding the minimum necessary to include one extra city in the previous minimum tour. This algorithm would work the same with a directed graph too. So where's the kaboom? -- Stupidly Pete.

Pete, you apply the algorithm N-1 times (or a fixed number of times) therefore you'll think you'll discover a fixed length path (in this case that would be N, as far as I can understand). You assume that the travelling salesman will never do loops (coming back to the same city). Or the poor salesman may occasionally wander off from a city on a dirt country road to reach a remote isolated village to sell his goods the villagers only to come back to the same city to continue the journey, because there's no place to go from that village other than the only town that the village is connected to. (YouCantGetThereFromHere). In other words you tacitly assume that your graph is so wonderfully connected that no loops will ever be necessary.

In less metaphoric terms, try to apply your algorithm to a less connected graph, maybe something like a tree. See how it goes. Here's your Christmas tree:

       a 
      /|\ 
     2 1 3
    /  |  \ 
   b   c   d
From wherever you start you have to visit "a" twice. -- Costin

Quite right Costin, and more generally I woke up realizing that what I described is strictly a HillClimbing algorithm. Lots and lots of ways of fooling it! -- Pete

I've been around this loads of times (this and the four colour theorem). The classic torture test is a bunch of cities on an equal grid e.g. a triangular grid. It isn't hard to see that there is no local information that can help you, therefore there cannot be a local or semi-local algorithm. Thus all combinations may have to be visited. --RichardHenderson.

I have a problem with the above example, which is that taking care of peninsulas is easy and doesn't negate his method. A simple algorithm could "trim" the above tree, as any peninsula is only solvable in one way. In other words, the trimmer would shave off everything but a, at which point the other algorithm could take over. Also also, this method above is called "adjacency matrices," and you can find the path-length-two matrix by squaring the path-length-one matrix; three - cubing; etc.


Cheating way:

1. Create an O(n!) reference solution and generate some moderately-sized problems, and/or use a generator to create problems with known answers.

2. Generate an initial program.

3. Apply each program to the problems.

   * If wrong answer: dead.

* If right answer: record steps taken.

4. Algorithms which took fewer steps are copied more times than algorithms without.

5. For each copy, go through code and roll dice to determine if code should be mutated, and how.

6. Goto 3 if(!bored)

7. /* bored now */ examine most-common algos.

EditText of this page (last edited January 2, 2013) or FindPage with title or text search