Блог

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

x_12 x_18 x_28 = 0

x_12 — x_18 — x_28 = 0

x_12 x_13 x_28 — x_38 = 0

-x_13 x_14 — x_38 — x_48 = — 2

-x_14 x_15 — x_48 — x_58 = -2

x_15 x_16 x_58 — x_68 = 0

Зная, что значения x_12 = 0, x_18 = 0 и x_28 = 0, можно создать алгоритм, который решает эту систему с другими переменными, предполагающими только значения 0 или 1.

 variables = x_12,x_13,x_14,x_15,x_16,x_18,x_28,x_38,x_48,x_58,x_68

equations = (x_12   x_18   x_28, 
         x_12 - x_18 - x_28, 
         x_12   x_13   x_28 - x_38, 
         -x_13   x_14 - x_38 - x_48   2,
         -x_14   x_15 - x_48 - x_58   2,
         x_15   x_16   x_58 - x_68)



solve((equations),variables)
  

это кажется простым, чтобы решить самостоятельно

 def check_equation(coefs,possible_solution):
    # of the form c1*A   c2*B   c2*C ... = 0
    return sum([a*b for a,b in zip(coefs,possible_solution)]) == 0

def simple_solver(coefs):
    nvars = len(coefs)
    for possible_solution in itertools.product([0,1],repeat=nvars):
        if check_equation(coefs,possible_solution):
           # this solution meets the condition
           yield possible_solution
  

чтобы представить вашу предыдущую проблему, вы бы использовали коэффициенты [1,1,1]

 list(simple_solver(1,1,1)) # should be [[0,0,0]]
# satisfy 1*A   1*B   1*C = 0
list(simple_solver(1,-2,1)) # should be [[0,0,0],[1,1,1]]
# satisfy 1*A   -2*B   1*C = 0
  

затем вы можете взять этот простой строительный блок и решить всю систему

 def system_solver(system_of_equations):
    solutions_pool = simple_solver(system_of_equations[0])        
    for next_eqn in system_of_equations[1:]:
        if(!solutions_pool)
            return None # no solutions
        solutions_pool = [possible_solution for possible_solution in solutions_pool if check_equation(next_eqn, possible_solution)]
    return solutions_pool # satisfy all constraints
                 
  

теперь я вижу, что они не всегда одинаковы 3 …. это немного сложнее, но это может дать вам место для начала