[Solved] Java: Traveling Salesman – Found polynomial algorithm

I’ll try to break this down to essentials. But first let me commend you for tackling a problem that’s “known” to be enormously hard. No progress can be made without risk taking.

You are approaching TSP in terms of a recursive expression for S(a, b, I), the length of a shortest path from city a to city b, a \ne b, passing through each city in the unordered set I exactly once.

With S in hand, the TSP is easy to solve. For the set of cities C, find

min( D(b, a) + S(a, b, C\a\b) ) over all pairs a, b drawn from C where a \ne b

Here D(x, y) = D(y, x) is the distance from city x to y and C\a\b is C with a and b removed.

The recursive expression you propose for S is

S(a, b, I) = min( D(a, p) + S(p, q, I\p\q) + D(q, b) ) 
               over all pairs p, q drawn from I where p \ne q ,  

The base cases are where I has zero or one element(s). These are pretty obvious.

You are proposing to cache values of S(a, b, I) so that no such computation is ever repeated. (This is called memoizing by the way.)

So what is the cost of this computation, or equivalently the size of the cache? We can write a recurrence for it, where the parameter n = |I| is the number of cities in the intermediate set:

C(n) = M(n, 2) C(n - 2) = ( n(n-1)/2 )  C(n - 2)
C(0) = C(1) = 1

Here M(n, m) is the combination of n things taken m at a time, n! / (m! (n-m)!)

We can solve this. For even n:

C(n) = n! /  2^(n/2)

I’ll let you work out the odd case.

For the tour among m cities, we’d need to repeat this for all city pairs and corresponding intermediate sets:

(m(m-1)/2) C(m-2) = m! / 2^(m/2-2)

So your method does avoid an exponential amount of work with respect to the naïve algorithm of generating all possible tours, but the factorial still dominates: this function is super-exponential.

NB on your other “stopping criteria:” Above is the cost of computing all possible values of S(a,b,I) exactly once. To get a poly time algorithm, you will have to come up with a scheme for skipping a super-exponential number (a,b,I) of triples entirely. It’s unlikely you can do this, but don’t let this dampen your enthusiasm.