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.

http://www.keck.caam.rice.edu/tsp/history.html -- with pictures of some large solutions

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:

Start with a weighted connectivity matrix M1 indicating the distances between immediately connected cities. Use *, meaning infinite, when you can't get from one city to another by only a single hop.
Construct a second matrix M2 thus: for each row i of M1 construct a new row i of M2 thus: for each row connected to i in M1 note the minimum cost of getting to a second city with no loops in the path. Use * for values where you can't get from one city to another in exactly 2 hops or where there's a loop.
Similarly construct a third matrix M3 from M2 for the minimum exactly 3 hop path costs.
Do this N-1 times and you have MN-1, the matrix for the N-1 hop minima. Pick the smallest of these minima - there's your TSP minimum.

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:

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.