1

A我对两个变量和有以下条件B：

[A,B] #:: 1..10,
(A #= 3) or (B #= 3),
((A #> 3 or B #>3) ->
     % expression 1
;
     % expression 2
)
%cntd

问题在第 2 行，求解器不知道 和 的值A，B如何在不指定第 2 行变量值的情况下决定继续哪个条件分支？

合理的行为是当求解器遍历变量的可能值时，根据变量的值来决定这个分支。但是，正如我发现的那样，在知道变量的值之前，它会通过这些表达式之一。防止这种情况的解决方案是什么？

4

2 回答 2

1

只要您坚持纯逻辑，约束编程就非常适合 Prolog。但是，正如您所展示的，人们不能自由地将诸如cut (!)和if-then-else (->;)之类的程序元素与约束逻辑混合。

if-then-else 或cuts 的使用仅在条件在“约束设置时间”被蕴含（即无条件地为真）或解除（无条件地为假）时才是安全的。实际上，这意味着此类条件不应包含问题变量（域变量等），而应仅包含先验已知的问题参数（常数）。专用的建模语言区分了这两件事，但 Prolog 没有。

如何不在约束模型中表达替代方案

以上意味着您不能使用 cut/if-then-else 来表达您想要表达的替代方案。简单地摆脱条件的承诺选择方面，并将其重写为纯析取可能很诱人。例如，您可以重写

( Usage #>= 1000 -> Rate#=7, Bonus#=100              % WRONG
;                   Rate#=9, Bonus#=0
)

作为纯粹的析取

( Usage #>= 1000, Rate#=7, Bonus#=100                % INEFFICIENT
; Usage #<  1000, Rate#=9, Bonus#=0
)

虽然现在这在逻辑上是正确的，但不要这样做！Prolog 通过回溯探索备选方案（使用分号(;)或多个子句表示），即首先急切地选择一个备选方案，然后再返回另一个备选方案。这通常会破坏对有效约束程序的任何希望！在约束程序中，所有搜索都应位于搜索/标记例程中。

具体化约束

如果替代方案的条件和分支都是具有具体实现的约束（即可以在布尔变量中反映约束的真实性的实现），那么您很幸运：您可以在帮助下重写整个条件替代方案用于具体化约束的特殊连接词（在 ECLiPSe 中：and, or, neg, =>, #=）。对于上面的例子：

Usage #>= 1000  =>  Rate#=7 and Bonus#=100,            % OK
Usage #<  1000  =>  Rate#=9 and Bonus#=0

或者

Usage #>= 1000 and Rate#=7 and Bonus#=100 or           % OK
Usage #<  1000 and Rate#=9 and Bonus#=0

不幸的是，只有基本的算术约束有具体化的版本，并且可以以这种方式组合！

使用其他内置约束

在某种程度上，处理备选方案是解决问题最困难的部分，许多内置约束解决了这个问题。因此值得检查问题是否可以在现有的内置约束之上建模，而在模型中没有任何显式析取。候选人是 element/3，table/2。disjunctive/2 和许多其他的。

延迟选择

最后的解决方案是推迟对替代方案的探索，直到可以明确确定条件的真相。在 ECLiPSe 中，使用延迟子句是最简单的。使用 OP 的示例：

delay choice(A, B) if var(A);var(B).     % wait for A,B to be known
choice(A, B) :-
    ( (A>3 ; B>3) ->                     % can now use normal Prolog tests
        write("expression 1")
    ;
        write("expression 2")
    ).

这有效，但只有在 A 和 B 都被实例化后才会起作用。如果在这种情况下，条件是可具体化的，我们可以做得更好：

choice(A, B) :-
    Bool #= (A#>3 or B#>3),
    delayed_choice(Bool).

delay delayed_choice(Bool) if var(Bool).
delayed_choice(1) :- write("expression 1").
delayed_choice(0) :- write("expression 2").

当域满足条件时，这将已经起作用：

?- choice(A, B), B #> 3.
expression 1

将一般析取变为约束

ECLiPSe在 library(propia)中有一个名为Generalized Propagation的漂亮功能。通过使用简单的注释，这可以有效地将 Prolog 析取转换为约束。从上面正确但低效的公式开始，我们可以写：

?- ( Usage #>= 1000, Rate#=7, Bonus#=100
   ; Usage #<  1000, Rate#=9, Bonus#=0
   ) infers most.

Usage = Usage{-1.0Inf .. 1.0Inf}
Rate = Rate{[7, 9]}
Bonus = Bonus{[0, 100]}
There is 1 delayed goal.
Yes (0.00s cpu)

正如 和 的域Rate所示Bonus，甚至在可以决定适用的替代方案之前，已经从析取中提取了有用的信息。

于 2019-05-15T15:24:26.800 回答
-1

问题是什么？ 重要的注意事项是在 if-else 中使用->（箭头）。当我们有表达式S -> T ; U时，S将被评估，如果它包含一些变量可能会对代码产生一些副作用。为了更清楚，尝试运行一些示例：

?-[A,B] #:: 1..10,
(A #= 3) or (B #= 3),
((A #> 3 or B #>3) ->
    write("expression 1")
;
    write("expression 2")
).

由于Aand的值B没有确定，所以条件总是为真，并且expression 1会打印出 的值。此外，结果是：

A = A{1 .. 10}
B = B{1 .. 10}
There are 6 delayed goals.
Yes (0.00s cpu)

正如你所看到的，Aand的边界B不会改变，因为它被暂停到未来的表达式，而我们没有改变，边界不会改变。

现在尝试不同的示例：

?- [A,B] #:: 1..10,
(A #= 3) or (B #= 3),
((A #> 3 or B #>3) ->
    write("expression 1")
;
    write("expression 2")
),
A = 3. % this line is added

由于A确定的值A #> 3不正确，但是呢B？是等于 3 还是大于 3？正如我们所说，条件部分将被执行！因此，最后一个约束B是B #> 3。除了执行之外write("expression 1")，结果是：

A = 3
B = B{4 .. 10}
Yes (0.00s cpu)

最后一个例子是：

?- [A,B] #:: 1..10,
(A #= 3) or (B #= 3),
((A #> 3 or B #>3) ->
    write("expression 1")
;
    write("expression 2")
),
A = 3,
B = 3. % this line is added

同样在这个例子expression 1中被打印出来，结果是：

No (0.00s cpu)

这是因为箭头的头部总是expression 1会被执行。

一种解决方案是使用;以下运算符：

[A,B] #:: 1..10, 
(
    (A = 3, B = 3, write('expression 21'))
    ; 
    (A = 3, B #> 3, write('expression 11'))
    ; 
    (A #> 3, B #> 3, write('expression 12'))
    ; 
    (A #> 3, B = 3, write('expression 13'))
), 
A = 3,
B = 5.

上面代码的结果是：

A = 3
B = 5
Yes (0.00s cpu, solution 1, maybe more)

它打印：

expression 21 expression 11

这意味着第一个分支出现故障，但它失败并自动回溯，并进入下一个案例！随着下一个案例的应用，一切顺利！

于 2019-05-15T10:52:00.733 回答