# traveling salesman problem Brute force and dynamic programming

*Traveling salesman problem Brute force and dynamic programming:* Given a set of cities and the distances between them, find the shortest path visiting each of a given set of cities exactly once and returning to the starting point. traveling salesman problem is a classical computer science problem.

Brute force solution: Traveling salesman problem

Compute the permutation of all the city and find the minimum cost. Here is permutation of all the cities ans their corresponding visiting cost.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
Tour 0123 and cost of this path is :84 Tour 0132 and cost of this path is :60 Tour 0213 and cost of this path is :68 Tour 0231 and cost of this path is :60 Tour 0321 and cost of this path is :84 Tour 0312 and cost of this path is :68 Tour 1023 and cost of this path is :60 Tour 1032 and cost of this path is :84 Tour 1203 and cost of this path is :68 Tour 1230 and cost of this path is :84 Tour 1320 and cost of this path is :60 Tour 1302 and cost of this path is :68 Tour 2103 and cost of this path is :84 Tour 2130 and cost of this path is :68 Tour 2013 and cost of this path is :60 Tour 2031 and cost of this path is :68 Tour 2301 and cost of this path is :84 Tour 2310 and cost of this path is :60 Tour 3120 and cost of this path is :68 Tour 3102 and cost of this path is :60 Tour 3210 and cost of this path is :84 Tour 3201 and cost of this path is :60 Tour 3021 and cost of this path is :68 Tour 3012 and cost of this path is :84 |

From above computed costs of each tour ,we can see that the minimum cost is 60.

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 |
#include<iostream> #include<limits.h> using namespace std; int c = 0; int cost = INT_MAX; // adjacency matrix of graph int graph[4][4] = { {0, 8, 12, 25}, {8, 0, 21, 10}, {12, 21, 0, 30}, {25, 10, 30, 0}}; void swap (int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } void calculate_cost (int *vertex, int n) { int i, sum = 0; for (i = 0; i <= n; i++) { sum += graph[vertex[i % 4]][vertex[(i + 1) % 4]]; } if (cost > sum) { cost = sum; } } void permute (int *vertex, int i, int n) { int j, k; if (i == n) { calculate_cost (vertex, n); } else { for (j = i; j <= n; j++) { swap ((vertex + i), (vertex + j)); permute (vertex, i + 1, n); swap ((vertex + i), (vertex + j)); // backtrack } } } int main () { int i, j; int vertex[] = { 0, 1, 2, 3 }; permute (vertex, 0, 3); cout <<"minimum cost:"<<cost<<endl; } |

**output:**

** minimum cost:60**

*Time complexity of traveling salesman problem Brute force and dynamic programming*

Brute force solution of tsp problem would be O(n!), so it will take lots of time for more number of cities. The dynamic programming approach breaks the problem into 2^{n}n subproblems. Each subproblem takes n time resulting in a time complexity of O(2^{n}n^{2}). We will discuss dynamic programming solution of traveling salesman problem in next postÂ http://wikistack.com/traveling-salesman-problem-dynamic-programming/

Ref:

http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/dynamic2.pdf

## Leave a Reply