Using bitmask in dynamic programming

Question

I learn about TSP and I stumbled upon a bit of masking to represent the whole combination of cities. I do not understand the logic of this. Please help me with 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 on how bit masking is used in this code?

Answer 1

Basically, a bitmask just helps you represent the cities visited , rather than using an array of logical ones.

For example, if we have 4 cities to represent this all 4 cities is visited, we can have a mask of 15, which is 1111b in binary(4 bits equal to 1).

If city 0 is not visited, 1110b 14, , 0 0 . (, , 0 )

, , ( , ), - .   ? 32- , .

, compute(int start, int set)?

• start: .
• set: .

,

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

npow - 1 , (? 2 ^ n - 1 , ), , (1<<i), , , , i.

masked=set&mask, , and 1, 1 0 , , set&mask, : 1, , i , 0.

So if(set == masked), , 0 ( ).

: , , ((set & (1<<i)) == 0)

Answer 2

- , .

f (u, s), u - node, , s - / . - , , , (, , ).

Answer 3

, , :

n = 3 nPow = 8, ?

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

..,

, #define min(a,b) a>b?b:a

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

, 5 20!!!

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

#define min(a,b) (a>b?b:a)