---

DP approach to the TSP

---

The DP approach to the TSP is of the 2ⁿ variety, at is it yields algorithms of 2ⁿ time and space complexities. Thus, the first question on the agenda must be: You must be kidding!? How can you seriously suggest such a procedure, the point being that such algorithms will only be able to cope with very small problems.

The counter argument reads as follows:

• In is discussion the TSP is used merely as a teaching aid and in is capacity it performs extremely well. We do not suggest here that DP offers a practical tool for solving large scale TSPs.

• Certain versions of the TSP, eg TSP with time-windows, are amenable to treatment by DP even in cases where n is large. Thus, even devoute practitioners may actually benefit from an understanding DP's approach to the TSP

We rest our case.

The DP algorithm we use here is based on the following DP functional equation: Let

DM[i,j]:= Distance between city i and city j
Cities := {1,2,3,...,n}
f(i,C) :=	shortest sub-route given that we are in city i and still have to visit the cities in C before returning to the home city.

It is convenient here to refer to city 1 as the home city.

Note that for a given city i>1, the set s can be any subset of cities excluding city 1 and city i. Thus, for each i>1 there are 2^n-2 distinct feasible values for C. And since there are n-1 feasible values for i>1, it follows that there is a total of 2^n-2(n-1) such (i,C) pairs. The problem of interest is associated with the pair (1,{2,...,n}), namely it represents the situation where we are in the home city (i=1) and still have to visit all the other cities (C={2,3,...,n}).

The following is an obvious property of the above definition of f :

f(i,Empty) = DM[i,1] , i = 2,3,4,...,n; Empty:= empty set.

In words: the best we can do if we are in city i and have no more cities to visit is return to the home city.

The following observation, typical of DP, is a bit more subtle:

f(i,C) = min { DM[i,j] + f(j,C\\{j}) : j in C }

Our DP procedure solves the TSP problem using this functional equation. That is, it first computes f(i,Empty) for all i in {2,...,n} and then computes the f(i,C) values by systematically generating feasible (i,C) pairs so that all the right-hand side values needed for computing f(i,C) have already been computed. We shall explain how this can be done elsewere. The procedure terminates with the evaluation of f(1,{2,...,n}). As explained above, the procedure generates a total of 1+2^n-2(n-1) pairs and solves the functional equation for these pairs.

Sooooo, when you use the DP Interactive Module respect the 2ⁿ complexity of the procedure!