在動態編程中使用Bitmasking

我正在學習TSP，並且我遇到了位掩碼來表示所有城市組合。我不明白它背後的邏輯。請幫助我。在動態編程中使用Bitmasking

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

請幫我瞭解在這段代碼中如何使用位掩碼？

來源

2014-09-05 Bad Coder

沒有具體的問題嗎？什麼是'TSP' – chouaib 2014-09-05 08:26:43

我問如何使用位掩碼我不能忽略它 – 2014-09-05 08:27:25

在這長的代碼你有這個位掩碼的行？ – chouaib 2014-09-05 08:28:15

基本上位掩碼只是幫助你代表訪問城市，而不是使用布爾數組。例如，如果我們有4個城市，那麼代表all 4 cities is visited，我們可以將掩碼設爲15，即1111b in binary（4位爲1）。

If city 0 is not visited，狀態只是1110b或14，你應該注意到在這種情況下位0是0。（同樣，如果你使用了一個布爾數組，0位置的值爲假）所以所有使用（移位，切換位）的技術只是修改一個特定位的位置。爲什麼這很有用？因爲它可以幫助你將整個狀態打包成一個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)，這意味着，城市我從一開始（或未訪問）爲0。

評論：這不是制定好使用位處理技術，如果我寫了這個代碼，我將使用((set & (1<<i)) == 0)

來源

2014-09-05 09:02:49

可以解釋我Compute（）函數以及它被使用 – 2014-09-05 09:33:38

@ user3865607更新 – 2014-09-05 09:40:38

要理解它，是有幫助的手動試試吧，OK，讓我們假設：

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)

來源

2014-09-05 08:45:19 chouaib

與bitmasking動態編程是隻是用來有效地計算數學旅行商問題遞歸的技術。

遞歸可以定義爲f（u，s），其中u是當前考慮的節點，s是可用/訪問城市的集合。我建議你在實現它之前首先閱讀關於遞歸的東西，因爲它背後的數學對於幫助你理解這個代碼非常重要（也許是唯一的方法）。

來源

2014-09-05 08:51:09

在動態編程中使用Bitmasking

回答

相關問題