找出多重方程的解是否存在(在N中)
考虑以下方程：
X > Y
X + Y > 7
Y <= 10
X >= 0
Y >= 0 我想找出是否有一个解决方案来满足所有这些(自然数)。
我不关心确切的解决方案，我只想知道有没有解决办法
我读过有关或其他线性规划库的文章，但我不确定它们是否能解决这样的问题。
特别是我不确定是否能解出两边都有变量的方程，比如
X > Y, or X + Y > Z 大多数例子是形式上的：
X * 10 + Y * 30 > constant 我需要它能够解出最大变量为4-8的系统，所有变量都在0-100的范围内。
我有另一个重要的限制，库需要快速。我需要能在0,00001秒的内解出类似7个方程的系统
回答 1
Stack Overflow用户
发布于 2014-05-21 21:53:57
有趣的问题。感觉很像整数背包问题。
首先，变量是否在两边都是无关的，因为下面这样的方程
X + Y > Z可以重写为
X + Y - Z > 0所以让我们假设所有的约束都是格式的
(const1 * var1) + ... + (const8 * var8) > const若要支持较少的变量，只需对其中一个常量使用值0。
可视化的方法是将两个变量的情况看作是确定与约束相对应的“线”的凸包。因此，每个约束都可以绘制为一条2D线，并且只允许在这条线的一侧设置值。
要对3个变量进行可视化，这与约束确定的平面凸包中是否有网格点(“自然数”)是一样的。
在这种情况下的问题是，解决方案应该只有自然数:这使得正规线性代数不可能，因为一个网格是强加的。我不知道有任何图书馆支持这种限制。
但是，自己写一个解决方案并不难:这个想法是通过积极地修剪每个数字来找到一个解决方案。
因此，在您的示例中:测试0到100范围内的所有X。现在转到下一个变量，并根据约束确定空闲变量的有效范围。为x == 8计算出:那么y的范围是：
- 0 ..。7由于约束x>y
- 0 ..。100由于约束x+y>7(因为x已经是8)
- 0 ..。9由于y< 10的限制
...and，我们在所有约束中重复这一点。Y的最后约束是0 ..因为这是最严格的约束。现在，对剩余的未绑定变量重复这个过程，如果您至少找到了一个解决方案，那么就完成了。
我预计这段代码在动态编程中大约是100行；计算时间很大程度上取决于输入，而且变化很大。
例如，一组需要很长时间的方程：
A + B + C + D + E + F + G + H > 400.5
A + B + C + D + E + F + G + H < 400.6作为一个人，我们可以推断，既然我们需要自然数，这些方程就没有解。但是，这个解决方案不能使用上面描述的方法，所有A的组合。在得出结论说没有合适的H之前，必须对G进行测试，因此它将研究所有的可能性。不是很愉快，但不可避免。
https://stackoverflow.com/questions/23793708
复制相似问题
腾讯云开发者
