Travelling Salesman Problem
A Quick Overview
Given a set of cities and distance between every pair of cities as an adjacency matrix, the problem is to find shortest route that visits all cities exactly once and returns to starting point.
1. Let city 1 be starting point and ending point. We can consider any point as a starting point since the route is cyclic.
2. Generate all possible permutations of cities which are (n-1)!.
3. Determine cost of each permutation and keep track of minimum cost permutation.
4. Return permutation with minimum cost.
Here, N is number of cities.
Here, we calculate the cost function cost() using a dynamic approach Cost ().
1. Create two primary data holders.
- List containing indices of cities based on input matrix of distance.
- Array containing our result
2. Traverse the given adjacency matrix tsp for all the cities, and update the cost if the cost of reaching any city is less than the current cost.
3. Calculate the minimum path cycle using above step and return their minimum cost.
How to implement these solutions in different languages?