解决（超过两个）线性不等式的系统 [英] Solving a system of (more than two) linear inequalities

问题描述

如果我使用

  diophantine（2 * x + 3 * y-5 * z-77）
  

我收到这个结果。

  {（t_0，-9 * t_0-5 * t_1 + 154，-5 * t_0-3 * t_1 + 77）} 
  

到目前为止还不错。然而，有时候人们可能会想把x，y和z约束为（比如说）是非负的。当我使用类似这样的方法时，我们可以使用这种方法< / p>

  reduce_inequalities（[0 <= t_0,0 <=  -  9 * t_0-5 * t_1 + 154,0 <=  -  5 * t_0-3 * t_1 + 77]，[t_0，t_1]）$ ​​b $ b  

我得到了：

  NotImplementedError：
不等式有多个符号感兴趣
  

sympy，sage，prolog，haskell或其他可免费获得的产品是否有解决此类问题的线性不等式系统的方法

谢谢！

解决方案

推理 CLP（FD）约束。

具体细节略有不同在不同的Prolog系统之间。请参阅系统手册了解更多信息，以及 clpfd 相关问题。

在您的情况中，我们可以从发布约束开始：

 
   -  2 * X + 3 * Y  -  5 * Z＃= 77。
 2 * X + 3 * Y＃= 5 * Z + 77。 
 

在这种情况下，对于所有纯Prolog程序，系统的答案是声明性地与原始的等效查询。这在这里没有什么帮助：系统只是稍微改写了原始约束。

您可以进一步限制，例如：

pre
？-2 * X + 3 * Y - 5 * Z＃= 77，
[X，Y ，0]，0 $，
2 * X + 3 * Y＃= 5 * Z + 77，
Y in 0 ..sup，
Z在0..sup。

根据要求，这个附加目标将变量限制为非负整数。系统的答案仍然没有帮助。

您可以使用 label / 1 来搜索具体的<强>解决方案即可。然而，这个所谓的标签要求所有的域都是有限，所以我们现在得到：

  -  2 * X + 3 * Y  -  5 * Z＃= 77，
 Vs = [X，Y，Z]，
 Vs ins 0..sup，
 标签（Vs）。 
 错误：参数未被充分实例化
 

好消息（某种意义上）是在任何情况下，我们都没有时间尝试所有 的可能性。所以我们不妨将自己限制在搜索空间的某个有限部分。例如：

 
？ -  2 * X + 3 * Y  -  5 * Z＃= 77，
 Vs = [X ，Y，Z]，
 vs ins 0..100 000 000 000 000 000 ，
标签（Vs）。 
 

使用此查询，您可以获得具体的整数作为解决方案：

 
 X = 0，
 Y = 29，
 Z = 2，
 Vs = [0，29，2]; 
 X = 0，
 Y = 34，
 Z = 5，
 Vs = [0,34,5]; 
 X = 0，
 Y = 39，
 Z = 8，
 Vs = [0，39，8]; 
 X = 0，
 Y = 44，
 Z = 11，
 Vs = [0，44，11]; 
等
 

由于您对线性约束的推理，CLP（Q）也可能是值得一试。

If I use

diophantine(2*x+3*y-5*z-77)

I receive this result.

{(t_0, -9*t_0 - 5*t_1 + 154, -5*t_0 - 3*t_1 + 77)}

Fine so far. However, on occasion one might like to constrain x, y and z to be (say) non-negative. When I use an approach like this<

reduce_inequalities([0<=t_0, 0<=-9*t_0 - 5*t_1 + 154, 0<=-5*t_0 - 3*t_1 + 77],[t_0, t_1])

I get:

NotImplementedError: 
inequality has more than one symbol of interest

Does sympy, sage, prolog, haskell or some other freely available product have means for solving systems of linear inequalities that arise in this way.

Thank you!

解决方案

To reason about integers in Prolog, you can use your Prolog system's CLP(FD) constraints.

The exact details differ slightly between different Prolog systems. Please see your system's manual for more information, and also clpfd for related questions.

In your case, we can start by simply posting the constraint:

?- 2*X + 3*Y - 5*Z #= 77.
2*X+3*Y#=5*Z+77.

In this case, and as for all pure Prolog programs, the system's answer is declaratively equivalent to the original query. This does not help a lot here: The system has only slightly rewritten the original constraint.

You can constrain this further, for example with:

?- 2*X + 3*Y - 5*Z #= 77,
   [X,Y,Z] ins 0..sup.
X in 0..sup,
2*X+3*Y#=5*Z+77,
Y in 0..sup,
Z in 0..sup.

As requested, this additional goal constrains the variables to non-negative integers. The system's answer still does not help a lot.

You can use label/1 to search for concrete solutions. However, this so-called labeling requires that all domains be finite, and so we currently get:

?- 2*X + 3*Y - 5*Z #= 77,
   Vs = [X,Y,Z],
   Vs ins 0..sup,
   label(Vs).
ERROR: Arguments are not sufficiently instantiated

The good news (in a sense) is that we don't have time to try all possibilities in any case. So we might as well restrict ourselves to some finite part of the search space. For example:

?- 2*X + 3*Y - 5*Z #= 77,
   Vs = [X,Y,Z],
   Vs ins 0..10 000 000 000 000 000 000,
   label(Vs).

With this query, you get concrete integers as solutions:

X = 0,
Y = 29,
Z = 2,
Vs = [0, 29, 2] ;
X = 0,
Y = 34,
Z = 5,
Vs = [0, 34, 5] ;
X = 0,
Y = 39,
Z = 8,
Vs = [0, 39, 8] ;
X = 0,
Y = 44,
Z = 11,
Vs = [0, 44, 11] ;
etc.

Since you are reasoning over linear constraints, CLP(Q) may also be worth a try.

这篇关于解决（超过两个）线性不等式的系统的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！