# traveling salesman problem dynamic programming

Traveling salesman problem dynamic programming. The tsp problem is considered to be difficult problem in computer science. Let us understand the classical traveling salesman problem with the help of below figure.

Let us consider the vertices 0,1,2,3 as cities. Cost to reach from one city to another city is given as the weight of the edge between them. For example the cost to reach from city 0 to city 1 is 8. The salesman is at the city 0. The salesman wants to visit each city starting from city 0 and return to the city 0 with minimum cost. The salesman has to visit each city exactly once. We have already discussed the brute force solution of the above problem on this post http://wikistack.com/traveling-salesman-problem-brute-force-and-dynamic-programming/.

*traveling salesman problem dynamic programming*

Here we are going to discuss an efficient approach for solving classical traveling salesman problem. The link https://github.com/evandrix/SPOJ/blob/master/DP_Main112/Solving-Traveling-Salesman-Problem-by-Dynamic-Programming-Approach-in-Java.pdf has very good explanation. It has java implementation. Here sample code in c/c++.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<iostream> #include<limits.h> #include<cmath> using namespace std; #define city 4 #define npow 16 // pow(2,city) // adjacency matrix of graph int graph[city][city] = { {0, 8, 12, 25}, {8, 0, 21, 10}, {12, 21, 0, 30}, {25, 10, 30, 0} }; int g[city][npow]; int p[city][npow]; int tsp (int start, int set) { int masked, mask, result = -1, temp; if (g[start][set] != -1) { return g[start][set]; } else { for (int x = 0; x < city; x++) { mask = npow - 1 - (int) pow (2, x); masked = set & mask; if (masked != set) { temp = graph[start][x] + tsp (x, masked); if (result == -1 || result > temp) result = temp; p[start][set] = x; } } } g[start][set] = result; return result; } int tsphelper () { for (int i = 0; i < city; i++) { for (int j = 0; j < npow; j++) { g[i][j] = -1; p[i][j] = -1; } } // init matrix g ,from distance matrix graph for (int i = 0; i < city; i++) { g[i][0] = graph[i][0]; } return tsp (0, npow - 2); } int main () { cout << "The min cost is :"; cout << tsphelper (); cout << endl; return 0; } |

## Leave a Reply