SWI-Prolog 和约束，库 CLP(FD) [英] SWI-Prolog and constraints, library CLP(FD)

问题描述

我正在使用 clpfd 库处理 (swi) prolog 中的约束.

I'm playing around with constraints in (swi) prolog using the clpfd library.

我试图确定一组约束何时封装或包含另一组约束，例如X＜4 封装了X＜7，因为只要前者为真，后者就为真.这可以很容易地用逻辑暗示来表示.但是，我无法让 #==> 运算符给我想要的结果，所以我求助于使用 not(Co1 #/ #Co2) ，其中 Co1 和 Co2 是约束.这对于单个约束来说很好，但是我想将约束的结合传递给 Co1 和 Co2.

I'm trying to identify when one set of constraints encapsulates or subsumes the other, e.g. X<4 encapsulates X<7 as whenever the former is true, the latter is true. This can be easily represented using logical implication. However, I couldn't get the #==> operator to give me the result I wanted, so I resorted to using not(Co1 #/ #Co2) where Co1 and Co2 are constraints. This is fine for individual constraints, but I then wanted to pass a conjunctions of constraints into Co1 and Co2.

现在问题来了.当我尝试时

Now here is the rub. When I try

X#<7 #/ #X#<4.

我回来了

X in 4..6,
X+1#=_G822,
X+1#=_G834,
_G822 in 5..7,
_G834 in 5..7.

(奇怪的是，在 Sicstus 中这样做会导致分段错误)

(oddly enough, doing this in Sicstus results in a segmentation fault)

当我通过时

X#<7,X#<4

我得到了想要的

X in inf..3.

显然，我不能将后者传递给 not(Co1 #/ #Co2)，但前者并没有给我想要的结果.谁能解释为什么这两种方法会产生不同的结果，以及如何让前者像后者一样行事?

Obviously, I can't pass the latter into not(Co1 #/ #Co2), but the former doesn't give me the result I want. Can anyone explain why the two approaches yield different results, and how I can get the former to act like the latter?

推荐答案

看来你正在处理 CLP(FD).这些求解器区分求解约束问题的设置阶段和标记阶段.

It seems you are dealing with CLP(FD). These solvers distinguish the setup phase and the labeling phase of solving a constraint problem.

CLP(FD) 求解器不会在设置阶段完全减少问题.因为它有机会在标记阶段减少变量范围.因此，在设置过程中可能会提出一个问题，该问题可以被其他求解器减少为否"，但不会使用 CLP(FD) 求解器.只有在标记过程中才会检测到否".

A CLP(FD) solver does not completely reduce a problem during the setup phase. Since it has the chance to reduce variable ranges during the labeling phase. Thus it could be that during setup a problem is posed which could be reduced by other solvers to "No", but it will not with a CLP(FD) solver. Only during labeling a "No" will be detected.

在设置阶段减少多少很大程度上取决于给定的 CLP(FD) 系统.一些 CLP(FD) 系统在设置阶段做更多的减少，而其他做更少.例如，GNU Prolog 使用一些索引传播，而 SWI Prolog 则没有.所以我们找到了例子，而不是你的例子:

How much reduction is done during the setup phase highly depends on the given CLP(FD) system. Some CLP(FD) systems do more reduction during the setup phase, while other do less. GNU Prolog for example uses some indexical propagation, whereas SWI Prolog does not. So we find for example, not your example:

SWI 序言:

?- X #< Y, Y #< Z, Z #< X.
Z#=<X+ -1,
X#=<Y+ -1,
Y#=<Z+ -1.

GNU 序言:

?- X #< Y, Y #< Z, Z #< X.
(7842 ms) no

此外，由于您使用的是具体化约束，因此它还取决于具体化的完成程度.但我想在目前的情况下它只是传播问题.我们现在找到您的示例:

Further since you are using reified constraints it also depends a little bit how clever the reification is done. But I guess in the present case its only a matter of propagation. We find now for your example:

SWI 序言:

?- X #< 4 #==> X #< 7.
X+1#=_G1330,
X+1#=_G1342,
7#>=_G1330#<==>_G1354,
_G1354 in 0..1,
_G1377#==>_G1354,
_G1377 in 0..1,
4#>=_G1342#<==>_G1377.

GNU 序言:

?- X #< 4 #==> X #< 7.
X = _#22(0..268435455)

在设置阶段减少更多工作量与将更多工作留给标记阶段之间进行权衡.整个事情也取决于给定的例子.但是当您在设置旁边也有标签时，您不会看到结果有任何差异:

There is a tradeoff between doing more reduction in the setup phase and leaving more work to the labeling phase. And the whole matter also depends on the given example. But when you have also labeling beside setup, you will not see any difference in terms of outcome:

SWI 序言:

?- X in 0..9, X #< 4 #==> X #< 7, label([X]).
X = 0 ;
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
X = 6 ;
X = 7 ;
X = 8 ;
X = 9.

GNU 序言:

?- fd_domain(X,0,9), X #< 4 #==> X #< 7, fd_labeling([X]).
X = 0 ? ;
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
X = 4 ? ;
X = 5 ? ;
X = 6 ? ;
X = 7 ? ;
X = 8 ? ;
X = 9

我没有使用 SICStus Prolog 或 B-Prolog 进行测试.但我猜他们会在 SWI-Prolog 和 GNU Prolog 附近的某个地方表现出来.

I didn't test with SICStus Prolog or B-Prolog. But I guess they will behave somewhere in the vincinity of SWI-Prolog and GNU Prolog.

如果您的域是真正的 FD，CLP(Q) 就不是真正的选择，因为它会错过一些否"减少，而 CLP(FD) 不会错过.例如以下在 CLP(FD) 中是不可满足的，但在 CLP(Q) 中是可满足的:

CLP(Q) is no real alternative if your domain is really FD, since it will miss some "No" reductions, which CLP(FD) would not miss. For example the following is unsatisfiable in CLP(FD), but satisfiable in CLP(Q):

X = Y + 1, Y < Z, Z < X.

再见

这篇关于SWI-Prolog 和约束，库 CLP(FD)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！