线性方程解和的最小化

Question

设x（i，j）为变量。所有变量和常量的值只能为0或1。另外，两个变量x（i，j）和x（k，l）之和等于(x(i,j)+x(k,l)) % 2对于以下格式的给定方程，可以使用什么算法来找到所有x（i，j）的解，从而使所有x（i，j）的和最小化：

x(0,0)  +x(0,1)  +x(0,2)  +x(1,0)  +0       +0       +x(2,0)  +0       +0       = 0
x(0,0)  +x(0,1)  +x(0,2)  +0       +x(1,1)  +0       +0       +x(2,1)  +0       = 0
x(0,0)  +x(0,1)  +x(0,2)  +0       +0       +x(1,2)  +0       +0       +x(2,2)  = 1
x(0,0)  +0       +0       +x(1,0)  +x(1,1)  +x(1,2)  +x(2,0)  +0       +0       = 0
0       +x(0,1)  +0       +x(1,0)  +x(1,1)  +x(1,2)  +0       +x(2,1)  +0       = 0
0       +0       +x(0,2)  +x(1,0)  +x(1,1)  +x(1,2)  +0       +0       +x(2,2)  = 1
x(0,0)  +0       +0       +x(1,0)  +0       +0       +x(2,0)  +x(2,1)  +x(2,2)  = 1
0       +x(0,1)  +0       +0       +x(1,1)  +0       +x(2,0)  +x(2,1)  +x(2,2)  = 1
0       +0       +x(0,2)  +0       +0       +x(1,2)  +x(2,0)  +x(2,1)  +x(2,2)  = 1

上述方程也可以看作：

^{pr2}$

例如，给定方程可以有以下两个解：

1. x（1,0）=0,0。在这种情况下，所有x（i，j）=3
2. x（2,2）=1且所有x（i，j）=0。在这种情况下，所有x（i，j）的和是1

什么算法可以用来找到以后的解。我试过用高斯消去法，但结果并不一致。在

更多说明： 关于方程是如何得到的更多解释：https://math.stackexchange.com/a/441588/299278

Answer 1

重新标记，基础是

XOR(a, b, c, d,       g      ) = 0
XOR(a, b, c,    e,       h   ) = 0
XOR(a, b, c,       f,       i) = 1
XOR(a,       d, e, f, g      ) = 0
XOR(   b,    d, e, f,    h   ) = 0
XOR(      c, d, e, f,       i) = 1
XOR(a,       d,       g, h, i) = 1
XOR(   b,       e,    g, h, i) = 1
XOR(      c,       f, g, h, i) = 1

我们可以删除相同的子短语来找到

^{pr2}$

如果我们对所有的基本规则求和并reduce-记住，XOR(a, a) = 0-我们发现

^{3}$

也就是说，任何解都必须包含1的奇数：1、3、5或7（我们可以简单地丢弃9，因为它必须与导致0的所有基本规则相冲突）。在

让我们试着找到一个只包含一个1的解决方案：

• 如果d或g是1，那么e或h必须是1；这给了我们至少两个1，这与我们的目标相矛盾。所以d，g，e，h都必须是0，f或者i必须是1。在
• 通过相同的参数，a，g，b，h为0，c或i为1。在
• 同样的参数a，d，b，e，c，f都是0
• 显然我一定是1岁
• 回过头来看，这是一个一致的解决方案，也是唯一包含单个1的解决方案。在

更一般地说，如果我们假设a、b、c、d、e的值是给定的：

f = XOR(b, c, e)
g = XOR(a, b, c, d)
h = XOR(a, b, c, e)
i = NOT XOR(a, e)

这使我们能够轻松地生成所有可能的解决方案：

from itertools import product

tests = [
    lambda a, b, c, d, e, f, g, h, i: a ^ b ^ c ^ d ^ g == 0,
    lambda a, b, c, d, e, f, g, h, i: a ^ b ^ c ^ e ^ h == 0,
    lambda a, b, c, d, e, f, g, h, i: a ^ b ^ c ^ f ^ i == 1,
    lambda a, b, c, d, e, f, g, h, i: a ^ d ^ e ^ f ^ g == 0,
    lambda a, b, c, d, e, f, g, h, i: b ^ d ^ e ^ f ^ h == 0,
    lambda a, b, c, d, e, f, g, h, i: c ^ d ^ e ^ f ^ i == 1,
    lambda a, b, c, d, e, f, g, h, i: a ^ d ^ g ^ h ^ i == 1,
    lambda a, b, c, d, e, f, g, h, i: b ^ e ^ g ^ h ^ i == 1,
    lambda a, b, c, d, e, f, g, h, i: c ^ f ^ g ^ h ^ i == 1
]

sols = []
for a, b, c, d, e in product([0,1], repeat=5):
    f = b ^ c ^ e
    g = a ^ b ^ c ^ d
    h = a ^ b ^ c ^ e
    i = 1 - (a ^ e)
    if all(test(a,b,c,d,e,f,g,h,i) for test in tests):
        sols.append(
            "{}   {} {} {} {} {} {} {} {} {}"
            .format(sum([a,b,c,d,e,f,g,h,i]), a,b,c,d,e,f,g,h,i)
        )
sols.sort()
print("\n".join(sols))

这给了

1   0 0 0 0 0 0 0 0 1
3   0 0 1 1 1 0 0 0 0
3   0 1 0 0 1 0 1 0 0
3   1 0 0 1 0 0 0 1 0
3   1 1 0 0 0 1 0 0 0
5   0 0 0 1 1 1 1 1 0
5   0 0 1 0 0 1 1 1 1
5   0 1 0 1 0 1 0 1 1
5   0 1 1 0 1 1 0 1 0
5   0 1 1 1 0 0 1 0 1
5   1 0 0 0 1 1 1 0 1
5   1 0 1 0 1 0 0 1 1
5   1 0 1 1 0 1 1 0 0
5   1 1 1 0 0 0 1 1 0
7   1 1 0 1 1 0 1 1 1
7   1 1 1 1 1 1 0 0 1

请注意，生成的解决方案中正好有一半通过了测试；这强烈地表明，应该可以使一个更依赖于变量，但我还没有找到一种方法。在

---

编辑：进一步阅读后，我们可以将我们的基础表示为一个增广矩阵

a b c d e f g h i x
         -
1 1 1 1 0 0 1 0 0 0
1 1 1 0 1 0 0 1 0 0
1 1 1 0 0 1 0 0 1 1
1 0 0 1 1 1 1 0 0 0
0 1 0 1 1 1 0 1 0 0
0 0 1 1 1 1 0 0 1 1
1 0 0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1 1 1
0 0 1 0 0 1 1 1 1 1

在进行高斯约化后，我们得到

^{8}$

如果我们将任意值赋给a..e，我们将得到

f g h i  x
     -
1 0 1 0  a
1 1 0 0  b
1 1 1 1 1-c
1 1 0 1 1-d
1 0 1 1 1-e    # over-constrained! Some choices of a..e will not work

这正是我之前得出的结论，但它是以一种更普遍适用的方式实现的。在

从这一点开始，您可以插入a..e的每一个组合，然后再次使用高斯约化来找到f..i的解决方案，或者象征性地解决问题

f g h i  x
     -
1 0 0 0  a ^ (1-c) ^ (1-d)
0 1 0 0  a ^ b ^ (1-c) ^ (1-d)
0 0 1 0  (1-c) ^ (1-d)
0 0 0 1  b ^ (1-d)
0 0 0 1  a ^ (1-e)      # over-constrained!

over约束在这里实际上很有用；注意b ^ (1-d) == a ^ (1-e)so e可以作为a, b, d的函数来找到。所以：

from itertools import product

for a,b,c,d in product([0,1], repeat=4):
    e = a ^ b ^ d
    f = a ^ c ^ d
    g = a ^ b ^ c ^ d
    h = c ^ d
    i = b ^ (1-d)
    print(a,b,c,d,e,f,g,h,i)

产生

0 0 0 0 0 0 0 0 1
0 0 0 1 1 1 1 1 0
0 0 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0
0 1 0 0 1 0 1 0 0
0 1 0 1 0 1 0 1 1
0 1 1 0 1 1 0 1 0
0 1 1 1 0 0 1 0 1
1 0 0 0 1 1 1 0 1
1 0 0 1 0 0 0 1 0
1 0 1 0 1 0 0 1 1
1 0 1 1 0 1 1 0 0
1 1 0 0 0 1 0 0 0
1 1 0 1 1 0 1 1 1
1 1 1 0 0 0 1 1 0
1 1 1 1 1 1 0 0 1