Минимизировать сумму решения линейного уравнения

Question

Пусть x (i, j) - переменная. Все переменные и константы могут иметь только значение 0 или 1. Кроме того, сумма двух переменных x (i, j) и x (k, l) равна (x(i,j)+x(k,l)) % 2 Для данного уравнения следующего формата, какой алгоритм может быть использован чтобы найти решение для всех х (I, J) таким образом, что сумма всех х (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 

для Например, данное уравнение может иметь следующие два решения:

1. x (0,2) = x (1,0) = x (1,1) = 1 и все x (i, j) = 0. В этом случае сумма всех x (i, j) = 3
2. x (2,2) = 1 и все x (i, j) = 0. В этом случае сумма всех x (i, j) равна 1

Какой алгоритм можно использовать для поиска более позднего решения. Я пробовал использовать gausian, но результат не последователен.

Больше объяснения: Более объяснение того, как было получено уравнение: 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 

то есть, любое решение должно содержать нечетное число 1s: 1, 3, 5, или 7 (мы можем тривиально отбросить 9, как это должно противоречить всех наших базисных правил, которые приводят к 0).

Давайте попытаться найти решение, содержащее только один 1:

• если либо д или г равно 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.

В более общем плане - если мы предположим, значения приведены для а, б, в, г, е:

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 

Обратите внимание, что ровно половина сгенерированных решений pas тестирование; это настоятельно предполагает, что можно сделать еще одну переменную зависимой, но я пока не нашел способа сделать это.

---

Edit: После дальнейшего чтения, мы можем представить нашу основу в качестве расширенной матрицы,

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 

После выполнения Gaussian редукции, мы получим

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) так 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