在条件开头使用整数悬浮时将如何处理 [英] How integer suspension will be handled when it is used in head of a condition
问题描述
对于两个变量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行的变量值的情况下决定继续哪个条件分支?/p>
合理的做法是，当求解器遍历变量的可能值时，根据变量的值来决定该分支. 但是，正如我发现的那样，在知道变量的值之前，它先经过了这些表达式之一.有什么方法可以防止这种情况发生?
Constraint编程很适合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 ， 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具有一个漂亮的功能，称为通用传播 库(propia).通过使用简单的批注，这可以有效地将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的域所示，即使在确定适用的替代方案之前，也已从析取物中提取了有用的信息.
I have the following conditions over two variable A and B:
[A,B] #:: 1..10,
(A #= 3) or (B #= 3),
((A #> 3 or B #>3) ->
% expression 1
;
% expression 2
)
%cntd
The problem is in line 2, the solver doesn't know about the value of A and B, how to decide which branch of condition will be continued without specifying the value of the variables at line 2?
The reasonable act is to decide on this branch based on the value of the variables when the solver traverse the possible values for the variables. But, As I found it goes through one of these expressions before knowing the value of the variables. What is the solution to prevent that?
Constraint Programming fits well with Prolog as long as you stick to pure logic. But, as you demonstrate, one cannot freely mix procedural elements such as cut (!) and if-then-else (->;) with the constraint logic.
The use of if-then-else or cuts is only safe if the condition is entailed (i.e. unconditionally true) or disentailed (unconditionally false) at "constraint setup time". In practice that means that such conditions should not contain problem variables (domain variables etc), but only problem parameters (constants) that are known a priori. Dedicated modelling languages distinguish these two things, but Prolog doesn't.
How NOT to express alternatives in constraint models
The above means that you cannot use cut/if-then-else to express the kind of alternative that you wanted to express. It might be tempting to simply get rid of the committed-choice aspect of the conditional, and rewrite as a pure disjunction. For example, you could rewrite
( Usage #>= 1000 -> Rate#=7, Bonus#=100 % WRONG
; Rate#=9, Bonus#=0
)
as a pure disjunction
( Usage #>= 1000, Rate#=7, Bonus#=100 % INEFFICIENT
; Usage #< 1000, Rate#=9, Bonus#=0
)
While this is now logically correct, do not do this! Prolog explores alternatives (expressed using semicolon (;) or multiple clauses) via backtracking, i.e. by eagerly choosing one alternative first, and going back to the other later. This will normally ruin any hope for an efficient constraint program! In a constraint program, all search should be located in the search/labeling routine.
Reified constraints
If both the condition and the branches of the alternatives are constraints that have a reified implementation (i.e. an implementation that can reflect the truth of a constraint in a boolean variable), you are in luck: you can rewrite the whole conditional alternative with the help of the special connectives for reified constraints (in ECLiPSe: and, or, neg, =>, #=). For the above example:
Usage #>= 1000 => Rate#=7 and Bonus#=100, % OK
Usage #< 1000 => Rate#=9 and Bonus#=0
or
Usage #>= 1000 and Rate#=7 and Bonus#=100 or % OK
Usage #< 1000 and Rate#=9 and Bonus#=0
Unfortunately, only the basic arithmetic constraints have reified versions and can be combined in this way!
Using other built-in constraints
In a way, dealing with alternatives is the most difficult part of problem solving, and many built-in constraints address this. Is is therefore worth checking whether the problem can be modelled on top of existing built-in constraints without having any explicit disjunctions in the model. Candidates are element/3, table/2. disjunctive/2 and many others.
Delaying the choice
A last resort solution is to delay the exploration of the alternatives until the truth of the condition can be unambiguously decided. In ECLiPSe this is easiest with delay clauses. Using the OP's example:
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")
).
This works, but will only act once both A and B are instantiated. If, as in this case, the condition is reifiable, we can do somewhat better:
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").
This will already act when the condition is satisfied by the domains:
?- choice(A, B), B #> 3.
expression 1
Turning general disjunctions into a constraint
ECLiPSe has a nifty feature called Generalised Propagation in library(propia). This can effectively turn Prolog disjunctions into a constraint, by using a simple annotation. Starting with the correct, but inefficient formulation above, we can write:
?- ( 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)
As the domains of Rate and Bonus show, useful information has been extracted from the disjunction, even before the applicable alternative can be decided.
这篇关于在条件开头使用整数悬浮时将如何处理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
