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.

traveling salesman problem dynamic programmingLet 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

traveling salesman problem dynamic programming

Here we are going to discuss an efficient approach for solving classical traveling salesman problem. The link has very good explanation.  It has java implementation. Here sample code in c/c++.


Related Contents to follow