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.

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

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