这是一个处理算法和按位异或运算的问题。我们得到x1*x2*x3*....*xn=P，其中 star( *) 操作表示 XOR（按位）操作， x1 到 xn 是正整数。P也是一个正整数。我们需要找到 min(a1+a2+a3+.....an) 使得这种关系成立--> (x1+a1)*(x2+a2)*(x3+a3)*....*(xn+an)=0。'+' 代表正常的加法运算。
问问题
2460 次
3 回答
4
重述为有界整数线性规划问题
该问题可以重述为以下有界 ILP（整数线性规划）问题。
Let x1,...,xN be as in the original problem, i.e. the goal is to minimize(a1+...+aN)
under the conditions (x1+a1) XOR ... (xN+aN) = 0, a1,...,aN >= 0.
The following is than an equivalent bounded ILP:
Find b[k,i] (0 <= k <= K, 1 <= i <= N) and s[k] (0 <= k <= K) such that
(A) b[k,i] in {0, 1} for all i=1..n, k=0..K,
(B) s[k] is an integer >= 0 for all k=0..K,
(C) sum(b[k,i]*2^k, k=0..K) >= x[i] for all i = 1..N,
(D) sum(b[k,i], i=1..N) = 2*s[k] for all k = 0..K
and minimize
sum(b[k,i]*2^k, i=1..n, k=0..K).
From a solution of the bounded ILP the ai's are obtained by
a[i] = sum(b[k,i]*2^k, k=0..(K-1)) - x[i]
b[k,i] 在这里只是 (xi+ai) 的二进制表示的第 k 位（条件 (A) 和 (C)）。为了使整体 XOR 为零，对于每个 k，偶数 b[k,i] 必须为 1。这由条件（B）和（D）表示。（请注意，（D）中的左手总和必须是即使它等于 2*s[k] 并且 s[k] 是整数）。
K，即表示所有（xi+ai）所需的位数（实际上是加一）必须事先确定。选择一个 K 使得所有 xi < 2^K 就足够了，即 ai 比最大的 xi 大一点。但是选择更大的 K 并不重要，最高位将简单地输出为零。如果 K 被选小，则 ILP 将无解。
解决方案的存在
忽略最小条件，问题可以重述为
给定 x, yz 且 x <= y，找到 a 和 b 使得 (x+a) XOR (y+b) = z
给定原始问题的一个实例，N >= 2。令 x=x1，y=x2，z=(x3 XOR x4 XOR ... xn)。如果找到合适的a和b，设置a1=a，a2=b，a3=...=an=0，得到原问题的解。
简化的问题通过以下方式解决（同样，忽略最小性）
- 如果 (y XOR z) >= x 那么 a: = ((y XOR z) - x), b := 0 是一个解 (*)
- 如果 (x XOR z) >= y 那么 a := 0, b := ((x XOR z) - y) 是一个解 (*)
- 否则，选择一个满足 (x+a) XOR z >= y 的 a。这样的 a 总是存在的，例如，您可以让 a := 2^k 与 2^k > max(x,y,z)。设置 b := ((x+a) XOR z) - y) 产生一个解 (*)
(*) 要查看这些确实是解决方案，您只需要应用一些代数。例如，在情况 (1) 中，将 a 和 b 代入后，得到：(x+(y XOR z)-x) XOR (y+0)。这与： (y XOR z) XOR y 相同，因此与：zqed Case (2) 的工作方式类似。在情况 (3) 中，您得到： (x+a) XOR (y+((x+a) XOR z)-y) = (x+a) XOR ((x+a) XOR z) = z。
这表明对于 N >= 2，总是存在解。
这些解决方案是否最小，我不知道。在情况（3）中，它显然取决于 a 的选择，所以至少你必须找出 a 的最佳选择。也可能是原始问题允许比简化问题更小的解决方案。Anway，也许这种重述可以帮助某人找出完整的解决方案。
顺便说一句，原始问题本质上让您完全自由地如何在 xi 上“展开”校正值 ai，这让我想知道这是否不等同于某种背包问题。如果是这样，找到一个最小的解决方案很可能是 NP 难的。
关于极简的观察
采取以下问题
(1+a1) XOR (3+a2) XOR (6+a3) = 0
在二进制中，即
(001b+a1) XOR (011b+a2) XOR (110b+a3) = 0
a1=a2=a3=0 的余数是 001b XOR 011b XOR 110b = 100b。因此，一个明显的解决方案是 a1=4,a2=0,a3=0。或者，a1=0,a2=4,a3=0。这个解决方案虽然不是最小的 - 以下解决方案更小
a1=1, a2=1, a3=0
它也是最小的，因为所有较小的解决方案只能有一个非零 ai，并且所有项 (2 XOR 3 XOR 6)、(1 XOR 4 XOR 6)、(1 XOR 3 XOR 7) 都是非零的。
这表明没有从底部（即最低位）向上工作的格力算法可以工作，因为这样的算法会跳过前两位，因为它们的残差最初为零。
它还表明，您不能从残差中选择某个非零位k并尝试通过将2^k添加到xi之一来将其归零。您有时必须将其添加到多个 xi 中才能找到最小的解决方案。
这让我更进一步相信找到一个最小的解决方案是一个相对困难的问题。
于 2012-09-30T10:47:54.500 回答
1
参考我的评论 - 一个尚未回答的问题：
负 ai 似乎是必要的：对于 N=1 的情况，a1=-x1 是问题的解决方案。因此，我假设在一般情况下也允许负 ai。
然后，对于 N=2，根本没有解决方案（“min”），除了在计算机中可以表示的（负）数存在限制之外：
对于 N=2 集：a1=x2+K 和 a2=x1+K。这产生：
(x1+x2+K) XOR (x2+x1+K) = 0，与 K 无关
总和 (a1 + a2) = (x1 + x2 + 2*K)
没有最小解：我们可以让 K 变得更负。
同样对于 N>2：对于 N 偶数，对 N=2（具有任意 K）进行成对“解决方案”；对于 N 奇数，单出 - 将其视为 N = 1 - 其余 N-1 将作为偶数 N 处理。
在所有情况下，您构造 ZERO XOR ZERO XOR ZERO ... = ZERO，其中 ZERO 始终是类型对 (am = xm+1 + K; am+1 = xm + K)，除非 N 为奇数，其中您还有另一个因素，即 {am = -xm) 类型。除了 N=1，解可以变成你喜欢的大负数。
于 2012-09-30T07:07:23.090 回答
1
也许第一次进入最小值 - N>1，所有 a(i) 都是积极的 - 沿着以下路线。让我先声明一些术语。
初始化 y(i) = x(i); y(i) 代表 (x(i)+a(i))，所以我们实际上初始化 a(i)=0（对于 i=1..N）。同样，定义 Q = y(1)^y(2)^...^y(N) （^ 代表 XOR）；最初 Q=P。
我们将调整 y(i) 以使 Q 为零，始终保持 y(i)>=x(i) - 即：a(i)>=0。
考虑每个数字 (x,y,a,P,Q) 的二进制（位）扩展，按 m=0,1,2,.. 对位进行编号：位 m 表示 2**m 值部分数字。
请注意，当且仅当具有相同非零位的 y(i) 的数量为奇数时，Q 中的一位非零。
进行如下操作。自上而下地扫描 Q 中的违规位（值 1），即：从最高（“当前剩余”）位 1 开始。让这成为位 #m。
我们有两种情况：
情况 A. 至少有一个 y(i) 在位 m 中为零。将 C 定义为所有此类 y(i) 的集合。
我们将选择其中一个（见下文）并将其 m 位设置为 1，即更改
y(i) = y(i)+(2**m). For the moment, just define INCREMENT=(2**m).
为了确定我们在集合 C 中的选择 y(i)，我们尝试通过尽可能大的 DECREMENT 部分补偿 INCREMENT (2**m)：
遍历位 m-1, m-2, ... 直到我们有一个位 #n ，其中 (1.) Q 有一个 1（即：我们希望删除的另一个有问题的位），并且 (2.) 在C 中的 y(i) 中至少有一个也是 1。
如果成功，则 (1.) 设置：
INCREMENT = INCREMENT - 2**n (note that this remains positive);
(2.) 减少集合 C 以仅保留那些具有位 #n 非零的 y(i)；(3.) 重复该过程，进一步向下扫描位。
一旦我们无法继续前进，就从 C 中任意选择剩余的 y(i) 之一并将其增加 INCREMENT。更新 Q。这通过添加从 Q 中删除位 {m,n,...}
(2**m - 2**n - ...)
对于所选的 y(i)，将其位 #m 设置为 1（为 0），并将其位 n,... 设置为 0（这些为 1）。
情况 B. y(i) 中没有一个在位 #m 中为零。在这种情况下：
迭代位 k=m+1, m+2, ... 直到至少两个 y(i) 在该位中有一个零。将 C1 定义为所有此类 y(i) 的集合，并复制到集合 C2。还定义
INCREMENT1 as (2**k - 2**m) and set INCREMENT2 = 2**k.
像我们在案例 A 中所做的那样处理 {C1, INCREMENT1}。
从集合 C2 中删除最终选择 y(i)。然后同样处理 {C2, INCREMENT2}。
重复所有这些直到 Q 中的所有位都为零。
我没有尝试证明这个过程产生了真正的最小值，但我确实相信这种方法可能是思考这种证明（的结构）的一个很好的起点。
于 2012-09-30T15:34:55.530 回答