线性方程解和的最小化

2021-03-01 03:12:26 发布

您现在位置:Python中文网/ 问答频道 /正文

设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

上述方程也可以看作:

^{pr2}$

例如,给定方程可以有以下两个解:

  1. x(1,0)=0,0。在这种情况下,所有x(i,j)=3
  2. x(2,2)=1且所有x(i,j)=0。在这种情况下,所有x(i,j)的和是1

什么算法可以用来找到以后的解。我试过用高斯消去法,但结果并不一致。在

更多说明: 关于方程是如何得到的更多解释:https://math.stackexchange.com/a/441588/299278