在动态编程中使用Bitmasking
我正在学习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; } 请帮助我在这段代码中如何使用位屏蔽？
基本上，位掩码只是帮助您表示访问过的城市 ，而不是使用布尔数组。
例如，如果我们有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<
npow - 1表示所有城市都被访问过，（为什么？只记下2 ^ n - 1二进制，你会理解）因此，当它减去(1<i 。
masked=set&mask如你所知，for and operator，如果两个位都是1则为1，否则为1，所以如果你set&mask ，结果是set中所有被访问的城市都是1，除非城市i已被访问过，它将变为0。
因此， if(set == masked) ，这意味着，城市i从一开始就是0（或未访问）。
评论 ：这不是很好地利用了位操作技术，如果我编写这段代码，我会用((set & (1<
使用位掩码的动态编程只是一种用于有效计算数学旅行商问题递归的技术。
递归可以定义为f（u，s），其中u是您当前正在考虑的节点，s是可用/访问城市的集合。 我建议你在实现它之前首先阅读有关递归的内容，因为它背后的数学对于帮助你理解这个代码（也许是唯一的方法）非常重要。
要理解它，手动尝试是有帮助的，好吧让我们假设：
n = 3然后nPow = 8 ，对吗？
现在让我们看一下int mask=(npow-1)-(1<
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)