2

我刚刚在http://codeforces.com/blog/entry/337阅读了一篇关于如何使用动态编程找到最短哈密顿路径的文章。

虽然伪代码有效，但我不明白为什么我必须在集合上使用 xor 运算符和 2^i。

为什么不直接从位掩码中减去当前访问的城市？为了使算法发挥作用，集合的异或是什么？

为了澄清这里是一段用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];
    }
4

1 回答 1

1

找到了我的问题的解决方案，^ 是一个位翻转。因此，如果您有一个位掩码并在掩码上使用 xor 运算符，您将翻转该位置的位。例如 1010 ^ (1<<1) 结果为 1000。同样适用于 1000 ^ (1<<1) = 1010。

减法也有效，但使用 xor 运算符，您可以肯定地知道您只在该位置触摸该位，而不是其他位置。图像 1000 - (1<1)，因此会产生完全不同的结果。因此，如果您 100% 确定 1 位于 i 位置，则可以使用减法，但 xor 更安全。

于 2013-06-19T17:37:41.237 回答