Bitmask DP/ TSP

Traveling Salesman Problem

Complexity: O(2^n * time take in the individual recursion or to process per element) .

Points to remember:

• This is applicable in cases when we try to enumerate all possible cases
• We try to reduce backtracking problems to use some kind of caching for eg. O(n!) to O(2^n) (2^n possible bit mask values)
• Constraints for n are low ≤ 30 .
• Bit mask is used as a parameter to cache values

Sample problem statement:

There is a new food delivery startup in town. For simplicity, assume that there are N delivery executives and N orders. Also we have estimated how much it would cost the startup if delivery executive ‘i’ delivers the order ‘j’. This considers all factors such as distance, traffic, customer priority, food value etc.Given a NxN cost matrix, we need to assign each order to an executive in such a way that the total cost to the startup is minimum.

Bitmask code: O ( n*n * 2^n )

For the given code we can also cache as per dp[node][mask] but in this case since we traverse sequentially anyway and the order does not matter , we can cache dp[mask] .

Input:

Hamiltonian Cycle Problem:

Given an adjacency matrix adj[][] of an undirected graph consisting of N vertices, the task is to find whether the graph contains a Hamiltonian Path or not. If found to be true, then print “Yes”. Otherwise, print “No”.

Points to remember:

1. The DP based solution is going to store a bitmask to mark the nodes visited and the vertex at which the path ends
2. Complexity is O(2^n * n*n )after caching
3. The code below uses only iterations and not recursions to go through the possibilities.

Reference :

• https://medium.com/swlh/problems-with-advanced-ds-bitmasking-and-dp-ce43cc6c26fb
• http://www.cs.ucf.edu/~dmarino/progcontests/modules/dptsp/DP-TSP-Notes.pdf