有没有可能生成一个算法，可以在Python中用二进制变量求解线性方程组？

Question

我很难定义一个算法，可以解决一个系统的线性方程组与二进制变量。 以下线性方程组给出的示例：

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)

Answer 1

这似乎是一个简单的解决你自己

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

为了表示您之前的问题，您可以使用coefs[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。。。。这有点难，但这可能会给你一个开始的地方