Travelling Salesman Problem

Posted: 5 Apr, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

Given a list of cities numbered from 0 to N-1 and a matrix 'DISTANCE' consisting of 'N' rows and 'N' columns denoting the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting city?

Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains an integer ‘N’, where ‘N’ denoting the number of the cities.

The next ‘N’ lines of each test case contain ‘N’ space-separated integers “DISTANCE[i][j]”, where DISTANCE[i][j] denotes the distance to jth city from the ith city. 
Output Format :
For each test case, return the minimum distance of the shortest possible route which visits each city exactly once and returns to the starting city.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
2 <= N <= 16
0 <= DISTANCE[i][j] <= 10^9

Time Limit: 1 sec
Approach 1

The idea here is to visit all possible permutations of visiting the vertex.

Example-


 

Consider the above graph one possible permutation is A -> B -> C -> D -> A. Similarly we try all permutations and calculate the cost of each of the routes and update the 'ANS' to a minimum such route.

If we notice B -> C -> D -> A -> B is a cyclic permutation of A -> B -> C -> D -> A. All the cyclic permutations will lead to the same 'ANS'wer. So, we can fix a particular vertex, say A and try for remaining (N - 1)! permutations.

We also need to keep in mind whether a particular vertex is visited or not. If it's visited then we don’t need to revisit them. 

There are many options to solve this problem, we can have an array of size ‘N’ and each element is either 0 or 1, 0 denoting the 'CITY' is visited and 1 denoting the 'CITY' is not visited. Here since the number of vertices is very less we can represent this array visited as a 'MASK' with ‘N’ bits, each bit corresponds to whether a particular 'CITY' is visited or not. If the i-th bit is set in the 'MASK' then the i-th 'CITY' is already visited, otherwise, the i-th 'CITY' is not visited. If the 'MASK' is equal to (1 << N) - 1 then this 'MASK' corresponds to all the cities being visited.

 

So, the recurrence to the above problem is:

GET_MIN_DISTANCE('MASK', 'CURRENT_CITY') = min ∀ 'CITY' (DISTANCE['CURRENT_CITY']['CITY'] + GET_MIN_DISTANCE('MASK' | (1 << 'CITY'), 'CITY').

Where, GET_MIN_DISTANCE('MASK','CURRENT_CITY') calculates the minimum distance to reach 'CURRENT_CITY' with set bits of 'MASK' denoting the cities visited till now.

Where 'MASK' | (1 << 'CITY')  sets the 'CITY'-th bit in 'MASK' i.e mark the 'CITY' as visited and DISTANCE['CURRENT_CITY']['CITY'] is the distance of 'CURRENT_CITY' to 'CITY'.

 

The algorithm is:

  • Declare a function GET_MIN_DISTANCE with parameters 'MASK' and 'CURRENT_CITY', where 'MASK' stores the information of the cities that are currently visited and 'CURRENT_CITY' denoted 'CITY' from where we want to calculate the shortest route.
    • If the 'MASK' is equal to (1 << N) - 1.
      • Return DISTANCE['CURRENT_CITY'][0], since we have fixed 'CITY' 0 and now we just need to return the cost of the path 'CURRENT_CITY' -> 0.
    • Declare an integer variable 'ANS' and set it to INFINITY.
    • Iterate from 'CITY' = 0 to N - 1,
      • If the 'MASK' & (1 << 'CITY') == 0, i.e the 'CITY'-th bit is unset in 'MASK' and this 'CITY' is unvisited.
        • Declare an integer variable tmpAns.
        • Set tmpAns to DISTANCE['CURRENT_CITY']['CITY'] + GET_MIN_DISTANCE('MASK' | (1 << 'CITY'), 'CITY').
        • Update 'ANS' to min('ANS', tmpAns).
    • Return the 'ANS'.
Try Problem