最短哈密爾頓路徑和bitmasking

我剛剛看了一下如何找到在這裏使用http://codeforces.com/blog/entry/337動態規劃最短哈密爾頓路徑的文章。最短哈密爾頓路徑和bitmasking

雖然僞代碼的工作原理，但我不明白爲什麼我必須考慮在集合和2^i上使用異或運算符。

爲什麼不直接從位掩碼中減去當前被壓縮的城市？爲了使算法實現這個算法，xor與這個集合有什麼關係？

澄清這裏是一塊用Java編寫的僞代碼：

public int calculate(int set, int i){ 

     if(count(set) == 1 && (set & 1<<i) != 0){ 
      return 0; 
     } 

     if (dp[set][i] != infinity){ 
      return dp[set][i]; 
     } 

     for (int city=0;city<n;city++){ 
      if((set & 1<<city) == 0) continue; 
      dp[set][i] = Math.min(dp[set][i], calculate(set^1<<i, city) + dist[i][city]); 
     } 
     return dp[set][i]; 
    }

來源

2013-05-14 Gooey

你試過重寫爲dp [set] [i] = Math.min（dp [set] [i]，calculate（set - 1 << i，city）+ dist [i] [city]） ;'？我認爲它也應該可以正常工作。 – songlj 2013-05-18 05:01:47

找到了解決我的問題，^是bitflip。因此，如果你有一個位掩碼並在掩碼上使用異或運算符，那麼你在那個位置上翻轉位。例如。 1010 ^（1 < < 1）導致1000 也是一樣的1000 ^（1 < < 1）= 1010

的減法也適用，但與XOR運算符，你肯定知道你只碰在那個地方，而不是別的。圖片1000 - （1 < 1），因此會導致完全不同的東西。因此，如果你100％確定1的位置在i位置，但是xor更安全，那麼可以使用減法。

來源

2013-06-19 17:37:41 Gooey

我明白了。我不認爲這很重要。兩者都是安全的。 XOR也改變進位。我認爲它也只適用於二進制邏輯。 – Bytemain 2013-06-19 19:10:23

最短哈密爾頓路徑和bitmasking

回答

相關問題