Travelling Salesman Problem

Hard
0/120
Average time to solve is 50m
profile
Contributed by
45 upvotes
Asked in companies
MicrosoftOperaMorgan Stanley

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
0 20 42 25
20 0 30 34
42 30 0 10
25 34 10 0
3
0 3 2
3 0 1
2 1 0
Sample Output 1 :
85
6
Explanation of Sample output 1:
For the first test case, 
The shortest possible route is 0 -> 1 -> 2 -> 3 -> 0 = 20 + 30 + 10 + 25 = 85. 

For the second test case,
The shortest possible route is 0 -> 1 -> 2 -> 0 = 3 + 1 + 2 = 6.

Sample Input 2:

2
1
5
2
0 2
2 0
Sample output 2:
5
4
Hint

Can you think of some brute force solution?

Approaches (2)
Brute-force

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'.
Time Complexity

O(N * N!), where ‘N’ is the number of cities.

 

Here we are trying every possible permutation which is of order (N - 1)! and a particular city can be placed at any of the N locations. So the overall time complexity is O(N * N!).

Space Complexity

O(N), where ‘N’ is the number of cities.

 

Since there are ‘N’ possible unique states and recursive stack can grow up to this. So, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Travelling Salesman Problem
Full screen
Console