clpfd 需要标记才能找到任何解决方案（使用 \+ 时）

Question

我正在尝试写类似 "you have the ball if you previously got the ball, and didn't give it since":

的内容

:- use_module(library(clpfd)).

time(T1, has_ball) :-
    time(T2, get_ball),
    T2 #=< T1,
    \+ (time(T3, give_ball),
         T2 #< T3, T3 #< T1).

time(0, get_ball).
time(2, give_ball).

这正确回答了有关特定时间 T 的直接问题（通过提供 T，例如带有标签）：

?- time(1, has_ball).
true.

?- T in 0..9, label([T]), time(T, has_ball).
T = 0 ;
T = 1 ;
T = 2 ;
false.

但是当要求找到所有有效时间 T 时，我只是得到错误：

?- time(T, has_ball).
false.

根据我的理解，clpfd 在没有标记的情况下对结果进行了一些过度近似，所以我本以为 "T in inf..sup, time(T, has_ball)." 会告诉我使用标记。但很明显我错了，现在我担心我可能会错过其他情况下的解决方案。有人可以帮我理解吗？

编辑： Isabelle Newbie 的回答让我意识到我的意思是：

time(HasBall, has_ball) :-
    time(GetBall, get_ball),
    GetBall #=< HasBall,
    \+ (time(GiveBall, give_ball),
        GetBall #< GiveBall #/\ GiveBall #< HasBall).

既然想法是"you still have the ball at time HasBall if you got it at some previous time GetBall, and did NOT give it SINCE"。所以 time(GiveBall, give_ball) 需要否定。这里用 #\ 替换 \+ 会产生一个新错误 ("Domain error: `clpfd_reifiable_expression' expected")，我将对此进行调查。

Answer 1

简短的回答是您不应该将 Prolog 否定 \+ 与 CLP(FD) 混合使用。 CLP(FD) 有自己的否定运算符来处理它的约束，写为 #\。所以你可以把你的谓词写成：

time(HasBall, has_ball) :-
    time(GetBall, get_ball),
    GetBall #=< HasBall,
    time(GiveBall, give_ball),
    #\ (GetBall #< GiveBall #/\ GiveBall #< HasBall).

我重命名了你的变量，因为我不太明白发生了什么。现在有点清楚了，但是否定的约束不应该被积极的 HasBall #=< GiveBall 代替吗？

在任何情况下，这都符合您的要求：

?- time(T, has_ball).
T in 0..2.

?- time(T, has_ball), label([T]).
T = 0 ;
T = 1 ;
T = 2.

?- time(1, has_ball).
true.

?- T in 0..9, label([T]), time(T, has_ball).
T = 0 ;
T = 1 ;
T = 2 ;
false.

为了更多地了解发生了什么，我们可以采用您的原始子句并将变量替换为常量值：

step1(T1) :-
    T2 = 0,
    T2 #=< T1,
    \+ ( T3 = 2, T2 #< T3, T3 #< T1 ).

step2(T1) :-
    0 #=< T1,
    \+ ( 0 #< 2, 2 #< T1 ).

step3(T1) :-
    0 #=< T1,
    \+ ( 2 #< T1 ).

所以在最后一步之后，当使用绑定变量和未绑定变量调用时，您的谓词的行为基本上如下：

?- T1 = 1, 0 #=< T1, \+ (2 #< T1).
T1 = 1.

?-         0 #=< T1, \+ (2 #< T1).
false.

这是因为在第一种情况下，最后一个目标是 \+ (2 #< 1)，它成功了，因为 2 #< 1 失败了。

但是如果不绑定T1，那么2 #< T1 成功:

?- 2 #< T1.
T1 in 3..sup.

所以它的否定 \+ (2 #< T1) 失败了。这个目标本质上说 "there are no numbers larger than two"，这是错误的。相反，CLP(FD) 否定在 "opposite" 约束条件下成功：

?- #\ (2 #< T1).
T1 in inf..2.

这几乎肯定在您的程序上下文中更有意义，因为它尊重数学属性不是 (A < B) 等同于 (A >= B):

?- 2 #>= T1.
T1 in inf..2.

编辑： 我错过了一个事实，即可能没有看到 give_ball 事件，在这种情况下，人们仍然会控制球。您不能使用 #\ 以您尝试的方式对其进行建模，因为 #\ 仅将应用于 CLP(FD) 约束（具体来说，"reifiable" ) 但不是 "normal" Prolog 目标。您也不能以这种方式混合这些级别。

所以你需要更明确地说明存在的两种情况：如果有以下两种情况，你还没有放弃球：

球在某个时间被放弃，但那个时间还没有到；或
球根本就没有放弃。

这里在Prolog中也是一样的，将应用Prolog取反的地方和应用CLP(FD)取反的地方分开：

has_not_given_up_ball(HasBall) :-
    time(GiveBall, give_ball),
    \# ( GetBall #< GiveBall #/\ GiveBall #< HasBall ).
has_not_given_up_ball(_HasBall) :-
    \+ time(_GiveBall, give_ball).

（同样，我认为您应该只使用 HasBall #=< GiveBall 而不是否定约束。）

然后您可以像这样调整您的定义：

time(HasBall, has_ball) :-
    time(GetBall, get_ball),
    GetBall #=< HasBall,
    has_not_given_up_ball(HasBall).

如果存在 time(2, give_ball) 事实，则其行为与以前一样，但有一个额外的选择点。如果我注释掉这个事实，它会正确地模拟出球没有被放弃，所以一个人会拿得更久：

?- time(T, has_ball).
T in 0..sup.

?- time(T, has_ball), label([T]).
ERROR: Arguments are not sufficiently instantiated
...

?- time(1, has_ball).
true.

?- T in 0..9, label([T]), time(T, has_ball).
T = 0 ;
T = 1 ;
T = 2 ;
T = 3 ;
T = 4 ;
T = 5 ;
T = 6 ;
T = 7 ;
T = 8 ;
T = 9.

只有不受限于有限域的时间标签才会出错，这是应该的。

clpfd 需要标记才能找到任何解决方案（使用 \+ 时）

clpfd requires labeling to find any solutions (when using \+)

prolog

negation

labeling

clpfd