I got the task to talk about an algorithm for travelling salesman problem (TSP) with dynamic programming.

My problem is, that I know how the TSP works and I've found a few brute force algorithms, but I just couldn't find a version with dynamic programming.

Wikipedia doesn't help much, it just confirms that there is one: "One of the earliest applications of dynamic programming is an algorithm that solves the problem in time O(n22n)."

What I've found is some pseudecode, but since it is full of math-symbols and that I don't know how to translate into programming language I'm a bit stuck...

**Pseudecode**

function algorithm TSP(G, n) for k := 2 to n do C({i, k}, k) := d1,k end for for s = 3 to n do for all S {1, 2, . . . , n}||S|| = s do for all k 2 S do {C(S, k) = minm6=k,m∈S[C(S − {k},m) + dm,k]} opt := mink6=1[C({1, 2, 3, . . . , n}, k) + d1,k end for end for end for; return (opt) end

Because of the LaTeX format the characters can't be copied, so take a look in the PDF...

Another pseudocode would be:

void travel (int n, const number W [] [], index P [] [], number & minlength) { index i, j, k; number D [1 .. n] [subset of V - {v1}]; for (i = 2; i <= n; i++) D [i] [⊘] = W[i] [1]; for (k = 1; k <= n - 2; k++) for (all subsets A ⊆ V - {v1} containing k vertices) for (i such that i ≠ 1 and vi is not in A){ D [i] [A] = minimum (W [i] [j] + D [j] [A - {vj}]); j: [vj ∊ A P[i] [A] = value of j that gave the minimum; } D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]); 2 ≤ j ≤ n P[1] [V - {v1}] = value of j that gave the minimum; minlength = D[1] [V - {v1}]; }

So my problem lies just with the algorithm. I can manage the input/output part, but just can't translate the pseudecode to C or C++ or even Java code. The other way around doesn't seem to work either, meaning I can't think of a way to translate the bruteforce algo into a DP algo.

Does anyone now how to implement a DP algorithm for the TSP? Or even better has anyone got a useable code? Or can anyone translate the math-stuff for me (a general programmer)?

I appreciate every help!

Thanks!

HP