最短哈密尔顿路径和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

回答

相关问题