Tag: 旅行推销员

在动态编程中使用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); // […]