在动态编程中使用Bitmasking

Question

我正在学习TSP,我遇到了掩盖代表所有城市组合的比特.我不明白它背后的逻辑.请帮帮我.

#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;
}

请帮助我在这段代码中如何使用位屏蔽？

Answer 1

基本上,位掩码只是帮助您表示访问过的城市,而不是使用布尔数组.

例如,如果我们有4个城市,那么为了表示all 4 cities is visited,我们可以将掩码设为15,即1111b in binary(4位为1).

If city 0 is not visited,状态只是1110b或14,你应该注意到在这种情况下位0是0.(类似地,如果使用布尔数组,则0位置的值为false)

所以使用(移位,切换位)的所有技术只是修改特定位的位置.为什么这有用？因为它可以帮助您将整个状态打包成32位整数,这可以很容易地用于动态编程.

那么compute(int start, int 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.

所以if(set == masked),这意味着,城市i从一开始就是0(或未经访问过).

评论:这不是很好地利用了位操作技术,如果我编写这段代码,我会用((set & (1<<i)) == 0)