Using Bitmasking in dynamic programming [closed]

Question

I am learning about TSP and i came across bit masking to represent all the combination of cities. I don't understand the logic behind it. Please help me in this.

#define size 10 //maximum 10 cities
#define min(a,b) a>b?b:a
#define sizePOW 1024 // 2^10

int n,npow,g[size][sizePOW],p[size][sizePOW],adj[size][size];

int compute(int start,int set)
{   
    int masked,mask,result=INT_MAX,temp,i;

    if(g[start][set]!=-1)
        return g[start][set];
    for(i=0;i<n;i++)
    {   
        mask=(npow-1)-(1<<i);
        masked=set&mask;
        if(masked!=set)
        {   
            temp=adj[start][i]+compute(i,masked);
            if(temp<result)
                result=temp,p[start][set]=i;
        }
    }
    return g[start][set]=result;
}

void getpath(int start,int set)
{
    if(p[start][set]==-1) return;
    int x=p[start][set];
    int mask=(npow-1)-(1<<x);  // What is the use of this line
    int masked=set&mask;
    printf("%d ",x);
    getpath(x,masked);
}
void TSP()
{   
    int i,j;
    //g(i,S) is length of shortest path starting at i visiting all vertices in S and ending at 1
    for(i=0;i<n;i++)
        for(j=0;j<npow;j++) 
            g[i][j]=p[i][j]=-1; 
    for(i=0;i<n;i++)
        g[i][0]=adj[i][0];
    int result=compute(0,npow-2);
    printf("Tour cost:%d\n",result);
    printf("Tour path:\n0 ");
    getpath(0,npow-2);
    printf("0\n");
}
int main(void) {
    int i,j;
    printf("Enter number of cities\n");
    scanf("%d",&n);
    npow=(int)pow(2,n);//bit number required to represent all possible sets
    printf("Enter the adjacency matrix\n");
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&adj[i][j]);
    TSP();
    return 0;
}

Please help me how the bit masking is used in this code ?

Answer 1

Basically bitmask is just help you to represent the visited cities, instead of using an array of boolean.

For example, if we have 4 cities, so to represent that all 4 cities is visited, we can have the mask is 15, which is 1111b in binary (4 bits are 1).

If city 0 is not visited, the state is just 1110b or 14, you should notice that bit 0 is 0 in this case. (Similarly, if you used a boolean array, the value for the 0 position is false)

So all the technique using (shift bit, toggle bit) is just to modify a specific bit's location. Why this is useful? Because it helps you to pack an entire state into a 32-bit integer, which can be easily used for dynamic programming.

So how is the compute(int start, int set) function?

• start : the current city.
• set : all the visited cities.

So

 mask=(npow-1)-(1<<i);
 masked=set&mask;

npow - 1 means all cities are visited,(why? just write down 2^n - 1 in binary, and you will understand) and thus, when it minus (1<<i), it means this is the state when all cities are visited, except city i.

masked=set&mask as you know, for and operator, it is 1 if both bit are 1 and 0 otherwise, so if you set&mask , the result is All the visited cities in set will be 1, except if city i is already visited, it will be turned to 0.

So if(set == masked), which means, city i is 0 from the beginning (or unvisited).

Comment: This is not making a good use of bit manipulation technique, if I wrote this code, I will use ((set & (1<<i)) == 0)

Answer 2

Dynamic programming with bitmasking is just a technique used to efficiently compute the mathematical traveling salesman problem recursion.

The recursion can be defined as f(u, s), where u is the node that you are currently considering and s is the set of available/visited cities. I'd suggest you to first read something about the recursion first before implementing it because the mathematics behind it can be very crucial to help you understand this code (and maybe the only way).

Answer 3

To understand it, it is helpful to try it manually, OK let's assume:

n = 3 then nPow = 8 , right?

Now let's see int mask=(npow-1)-(1<<x);

x = 0;
mask = (8-1) - (1<<0);
     = 7 - (1 right-shifted 0 times)
     = 0111 - 1;  // in binary
     = 0110;  which means the bit number 0 was masked

x = 1;
mask = (8-1) - (1<<1);
     = 7 - (1 right-shifted 1 times)
     = 0111 - 10;  // in binary
     = 0101;  which means the bit number 1 was masked

and so on,

IMPORTANT

Not part of the answer to your problem but be careful with your macro #define min(a,b) a>b?b:a

try

int a = 10,b = 5,c;    
c = min(a, b)*4;

It drives you crazy when you get 5 as output instead of 20 !!!

c = min(a,b)*4
  = a>b? b:a*4
  = b // in this case 

to avoid it use extra parentheses #define min(a,b) (a>b?b:a)