最小化线性方程解的和

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

上式也可以看成：

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

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

x(0,2)=x(1,0)=x(1,1)=1 并且所有 x(i,j) = 0。在这种情况下，所有 x(i,j) 的总和= 3
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

我们可以去掉相同的sub-phrases来找到

# removing rows
XOR(d, g) = XOR(e, h) = NOT XOR(f, i)    # -(a, b, c)
XOR(a, g) = XOR(b, h) = NOT XOR(c, i)    # -(d, e, f)
XOR(a, d) = XOR(b, e) = XOR(c, f)        # -(g, h, i)
# removing columns
XOR(b, c) = XOR(e, f) = NOT XOR(h, i)    # -(a, d, g)
XOR(a, c) = XOR(d, f) = NOT XOR(g, i)    # -(b, e, h)
XOR(a, b) = XOR(c, e) = XOR(g, h)        # -(c, f, i)

如果我们对所有基础规则求和并减少 - 请记住，XOR(a, a) = 0 - 我们会发现

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

也就是说，任何解决方案都必须包含奇数个 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

进行高斯降维后，我们得到

a b c d e f g h i x
-------------------
1 0 0 0 0 1 0 1 0 0
0 1 0 0 0 1 1 0 0 0
0 0 1 0 0 1 1 1 1 1
0 0 0 1 0 1 1 0 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0     #
0 0 0 0 0 0 0 0 0 0     # under-constrained - multiple solutions
0 0 0 0 0 0 0 0 0 0     #
0 0 0 0 0 0 0 0 0 0     #

如果我们为 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-constraint在这里其实很有用；请注意 b ^ (1-d) == a ^ (1-e)，因此 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

最小化线性方程解的和

Minimize the sum of solution of linear equation

python

algorithm

optimization

linear-algebra