DYNAMIC PROGRAMMING EXAMPLE
TRAVELING SALESPERSON PROBLEM

The traveling salesperson problem finds application in a variety of situations. Suppose we have to pick up mail from mail boxes located at n different sites. An n+1 vertex graph can be used to represent the situation. One vertex represents the post office from where the post van starts and to which it must return. Edge is assigned a cost equal to the distance from site i to site j. The route taken by the postal van is a tour, and we are interested in finding a tour of minimum length.

Similarly this problem can be linked to a problem of data sending through one computer to another (which are widely separated). Then the routing path that they used to transfer the data is again one of the example of this kind. The shortest routing path is selected so that the data transfer speed is maximum and in the minimum time.


So now lets mathematically analyze this problem
:
Assumption: that the tour starts from the first vertex and ends at the first vertex too.
Every tour consists of an edge <1,k> for some k € V – {1} and a path from vertex k to vertex 1. The path from vertex k to vertex 1 goes through each vertex V-{k,1} exactly once. It is easy to see that if the tour is optimal , then the path from k to1 must be the shortest k to 1 path going through all vertex in V-{1,k}. Hence the principle of optimality holds. Let g(i,S) be the length of the shortest path starting at vertex i, going through all the vertex in S, and terminating at vertex 1. The function g(1,V-{1}) is the length of an optimal salesperson tour. From this we have


g(1,V-{1})=min 2<=k<=n{c1k + g(k, V – {1,k})}

Generalizing it we get

g( i ,S) = min j € S{cij + g( j , S - {j})}

The first equation can be solved for g(1,V-{1}) if we know g(k, V – {1,k}) for all choices of k. The g values can be obtained by using the second equation.

Now g(i, null) =cij, 1<=i<=n , clearly visible. Hence we can use equation 2 to obtain g(i,S) for all S of size 1. After that we have g(i,S)for S with |S| = 2, and so on. when |S|< n-1, the values of i ans S for which g(i,S) is needed are such that i != 1, 1
€ S, and i € S.
So this was the solution of traveling salesperson problem by dynamic method. It is a little tough and may take two to three readings of this lesson to understand it completely.

For its C language code, you can refer to this link. It is done by some other member, but it is preferred if you make your own c code.

Non-profit Tax ID # 203478467