可以根据特定和的结果计算变量值的算法

Question

这可能是一个重复的问题，但我无法在堆栈溢出时找到它。

拿一些变量，这些变量都代表了某种可能性。这意味着所有变量的值都介于0和1之间（包括两者）。这些的价值是未知的。但是，我有一些方程式，其中包含一些或所有这些变量，其结果是已知的。

例如，取变量a，b，c，x和y。它们的值都是介于0和1之间的未知数字（包括两者）。我有以下等式：

1: a + b + c = 1
2: a + b + x = 2
3: b + c + y = 2
4: a + x <= 1    ->    0 <= a + x <= 1
5: c + y <= 1    ->    0 <= c + y <= 1

解决这个问题会得到以下结果：

2: a + x + b = 2
   (something between 0 and 1) + b = 2
   b = 2 - (something between 0 and 1)
   1 <= b <= 2
   b = 1 (since 0 <= b <= 1 applies too)

1: a + b + c = 1
   a + 1 + c = 1
   a + c = 0
   a = -c
   a = 0  (since 0 <= a <= 1 and 0 <= c <= 1 apply)
   c = 0

2: a + b + x = 2   |   3: b + c + y = 2
   0 + 1 + x = 2   |      1 + 0 + y = 2
   x = 1           |      y = 1

-> a = 0, b = 1, c = 0, x = 1 and y = 1

我在纸上解决了这个问题，我的实际目的是通过为每个未发现的单元分配一个变量x a b c y来证明以下的扫雷行情。由于x，y和b结果是一个，他们可以被标记：

我的一般目的是使用这种技术解决扫雷板，但它可以用在其他软件中。但是，如果我想要一台计算机使用这种技术解决扫雷板，那么一个计算器必须使用算法来解决任何数量的变量和任意数量的方程式。是否有通用算法可以做到这一点？如果有，我应该如何实现该算法？

使事情变得明显

• 等式是一个变量或一些变量的总和，具有有限或恒定的结果，总是正的。
• 变量是0和1之间的未知值（包括两者）。
• 该算法采用具有相应变量名称的变量数量以及定义某些变量的等式。
• 该算法尝试计算尽可能多的值。无法确定的值仍未确定。

Answer 1

通常，您有一个N维向量空间，N个自变量可以在该空间上变化。每个约束都定义了向量空间的一个区域，所有这些区域的交集都是您想要确定的区域。实际上，您正在寻找该区域最简单（最简单）的描述，因为该区域已经由约束集合描述。有三种可能性：第一，该地区没有解决方案;第二，该地区的解决方案数量有限;第三，该地区存在无限多的解决方案。

您的第一步可能是将方程式（如果有的话）视为一个方程组，并使用算法求解方程组，以便尽可能地从方程式求解。如果没有别的，删除一些变量将有助于下一步。

1: a + b + c = 1
2: a + b + x = 2
3: b + c + y = 2

1: a = 1 - b - c
2: 1 - b - c + b + x = 2
3: b + c + y = 2

1: a = 1 - b - c
2: c = x - 1
3: b + x - 1 + y = 2

1: a = 1 - b - c
2: c = x - 1
3: b = 3 - x - y

1: a = y - 1
2: c = x - 1
3: b = 3 - x - y

这是我们可以做到的。接下来，我们将完整的不平等系统替换为：

A: 0 <= a <= 1
B: 0 <= b <= 1
C: 0 <= c <= 1
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 0 <= a + x <= 1
G: 0 <= c + y <= 1

A: 0 <= y - 1 <= 1
B: 0 <= 3 - x - y <= 1
C: 0 <= x - 1 <= 1
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 0 <= y - 1 + x <= 1
G: 0 <= x - 1 + y <= 1

A: 1 <= y <= 2
B: 3 >= x + y >= 2
C: 1 <= x <= 2
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 1 <= y + x <= 2
G: 1 <= x + y <= 2

此时，您需要隔离查找每个变量的约束（如果有的话）并找到这些约束的交集。

A: 1 <= y <= 2 \
                > taken together, the only solution is y = 1
E: 0 <= y <= 1 /  this is the intersection of intervals [0,1] and [1,2]

C: 1 <= x <= 2 \
                > taken together, the only solution is x = 1
D: 0 <= x <= 1 /  this is the intersection of intervals [0,1] and [1,2]

B: 3 >= x + y >= 2 \  taken together, this means x + y = 2
F: 1 <= y + x <= 2  > this is the intersection of [1,2] and [2,3]
G: 1 <= x + y <= 2 /  note that G turns out to be redundant after subbing

解x = 1，y = 1与我们的不等式系统一致。这是唯一的解决方案。我们可以在我们的方程组中反向替换以获得其他变量的值：

1: a = y - 1
     = 1 - 1
     = 0
2: c = x - 1
     = 1 - 1
     = 0
3: b = 3 - x - y
     = 3 - 1 - 1
     = 1

因此解决方案a = 0，b = 1，c = 0，x = 1，y = 1起作用并且是唯一的解决方案。几乎所有这些步骤都应该是您可以自动化的事情。