1

如何求解具有三个方程和 5000-20000 个变量（可以是 0 或 1）的多元非线性方程组？

系统可能有很多解决方案，但我只需要找到其中一个。

谢谢

4

2 回答 2

4

如果您的方程是纯布尔值，您可以使用也称为 SAT 的“可满足性求解器”。您的问题正是 SAT 求解器的设计目标。其中许多是开源的，最著名的是miniSAT。您只需实例化一个求解器，将您的方程式（也称为“子句”）输入其中并请求解决方案。求解器将在找到第一个合适的变量组合时停止。

如果我理解正确，您的不是纯粹的布尔值，而是布尔变量的算术。有一些技巧可以使它们适应 SAT。例如，将方程 x1x2+x3x4+x5x6x7=2 添加到 SAT 求解器的常用方法如下：引入新变量 v1=x1x2，v2=x3x4，v3=x5x6x7，然后添加子句“恰好两个 (v1, v2,v3) 是真的”（miniSAT 有一个生成器用于这种和类似类型的子句）。

如果某些系数不是 0 和 1，您可能需要对称为 SMT（可满足性模理论）的 SAT 求解器进行特殊扩展。其中一些程序也可作为开源程序使用。

于 2013-11-05T22:11:58.500 回答
2

二进制数（a = 0 或 1）的好处在于，对于 b > 0 的所有值，a^b = a。因此，通过消除所有多项式项的简单利用，您的“非线性”方程将变为线性。

当你有许多线性方程时，问题就变成了：系数的什么组合（我假设系数是线性的）给了我这个方程的常数项？原则上，您应该能够消除两个变量（因为您有三个方程）并最终得到一个方程。满足这一点的 1 和 0 的任何组合现在都可以解决您的问题。您将不得不查看系数 - 是否有一个等于常数？然后你就有了答案（那个位 = 1，其他的都是 0）。或者是否有一对系数相加成常数？当您开始组合更多项时，要测试的排列数量会迅速增加。我想不出一个“聪明”

更新给出的例子

x1 + x2 + x3 + x4 + x5 = s
x1x2 + x2x3 + x3x4 + x4x5 = t

我们可以注意到以下几点：

  1. 设置为的位数1必须为 == 5（来自第一个等式）
  2. t 必须 < s（因为没有新的术语出现，而且我们有术语的产品）

在像这样的玩具示例中，我们实际上可以进行详尽的搜索。当术语的数量变得更大时，其大小s将t推动复杂性。需要注意的几点

n 位总和为 s = 的可能组合数n!/(n-s)!s!。并且使用最常作为常用术语出现的因素来考虑“复合”方程是值得的。在上面，你会看到

x2(x1+x3) + x4(x3+x5) = t

现在我们可以看到，如果 t > 2，我们必须同时拥有x2=1和x4=1; 其他地方也可能进行类似的简化。

因为你实际上只有三个方程，我会寻找方法将尽可能多的元素设置为零（使用类似上面的方法），然后对剩下的那些进行详尽的搜索......

于 2013-11-05T21:38:58.050 回答