带约束的 Prolog 组合

Question

我正在寻找一种方法来在给定一组特定约束的情况下找到所有可能的解决方案。我在学校学过序言，但已经有一段时间了，所以我认为我还是个新手。我想要实现的是这样的:

fC(U,V,X,Y,Z):- 
    (U*2 + V - Y -(2*Z)) =< -5,
    (U*2 + V - Y -(2*Z)) >= -108,
    (U+V+X+Y+Z) =:= 54. 

U、V、X、Y 和 Z 是非负数。他们只有 2 条规则来计算它们:在 -5 和 -108 之间(当乘以我试图在上面的代码中制定的特定权重时)并加在一起正好是 54。

我尝试生成 5 个 0 到 54 的列表，找到所有组合，然后检查它们以检查我的“约束”，我很快就耗尽了内存，所以我一定是做错了什么。

亲切的问候，

耶勒

Answer 1

对于整数，使用 clpfd 很容易限制。例如，在 SICStus Prolog 或 SWI 中:

:- use_module(library(clpfd)).

fC(U,V,X,Y,Z):- 
    U*2 + V - Y -2*Z #=< -5,
    U*2 + V - Y -2*Z #>= -108,
    U+V+X+Y+Z #= 54. 

您已经通过最一般的查询获得了剩余目标:

?- fC(U, V, X, Y, Z).
X+U+V+Z+Y#=54,
2*Z+Y#=<2*U+V+108,
2*U+V+5#=<2*Z+Y.

在这种情况下，这本身并没有多大帮助。

要获得具体的解决方案，请使用labeling/2。例如:

?- fC(U, V, X, Y, Z), Vs = [U,V,X,Y,Z], Vs ins 0..sup, label(Vs).

约束Vs ins 0..sup表明所有变量都是非负的。在 SICStus Prolog 中，使用 domain(Vs, 0, super)。

示例解决方案:

U = V, V = X, X = Y, Y = 0,
Vs = [0, 0, 0, 0, 54],
Z = 54 ;
U = V, V = X, X = 0,
Vs = [0, 0, 0, 1, 53],
Y = 1,
Z = 53 ;
etc.

对于有理数的约束，请查看 clpq约束和库(clpq)。