最小化线性方程的解和

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

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

# 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!

过度约束在这里实际上很有用;请注意，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