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.

traveling salesman problem Brute force and dynamic programming

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.

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.

#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 2nn subproblems. Each subproblem takes n time resulting in a time complexity of O(2nn2). 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



Related Contents to follow