问题描述
我正在学习有关TSP和我碰到位掩码重新present城市的所有组合。我不明白它背后的逻辑。请帮我在这。
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;
}
请帮我怎么位掩码用于此code？
Please help me how the bit masking is used in this code ?
推荐答案
基本上掩码只是帮助你的重present拜访的城市，而不是使用布尔数组。
Basically bitmask is just help you to represent the visited cities, instead of using an array of boolean.
例如，如果我们有4个城市，所以要重新present的所有4个城市被访问，我们可以有掩码是15，这是 1111B二进制（4位是1）。
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).
如果城市0没有访问，国家只是 1110B 或14，你应该注意到位0是0在此情况下。 （同样，如果您使用一个布尔数组，为0的位置值为false）
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)
因此，所有的技术使用（移位，触发位）仅仅是修改特定位的位置。 为什么这是有用的？因为它可以帮助你收拾整个州成一个32位的整数，它可以容易地用于动态编程。
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.
那么，如何在计算（INT开始，诠释设置）功能？
- 启动：目前我市
- 设置：所有被访问的城市
于是
mask=(npow-1)-(1<<i);
masked=set&mask;
NPOW - 1 意味着所有的城市都参观了，（为什么只写下来2 ^ N - 1的二进制文件，你就会明白），因此，当它减（1＆LT;＆LT;我），这意味着这是当所有城市被访问，除了市州我。
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.
屏蔽=设置和放大器;面膜如你所知，对于和操作符，它是1，如果两个位都是1否则为0，因此，如果您设置和放大器;面膜，其结果是所有受访城市中集将是1，除非城市我已访问，将变为0。
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.
所以如果（套==屏蔽），这意味着，城市，我是从0开始（或者未访问）。
So if(set == masked), which means, city i is 0 from the beginning (or unvisited).
注释：这是不是在一个良好的使用位操作技巧，如果我写了这个code，我将使用（（集及（1＆LT; ＆LT;我））== 0）
Comment: This is not making a good use of bit manipulation technique, if I wrote this code, I will use ((set & (1<<i)) == 0)
这篇关于在动态规划使用Bitmasking的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！