SDT Course, Constraints final –
making the pruning more efficient
This page gives some hints on how to make the
constraint endviews/5 do more pruning.
It may be worthwhile to implement some variation of
a firstpos/2 constraint, with the following
specification:
% firstpos(+L, +K): in list L, the first positive number is K.
% It can be assumed that L is proper (i.e., not open-ended). The elements of L are FD-variables
% or integers; it can be assumed that all elements of L are non-negative. K is a given positive integer.
% firstpos/2 should prune as much as possible, but not perform labeling nor create any choice points.
Note that the argument K is an integer and not a
constraint variable. Given this, you can easily add a membership
constraint (see slide 234) which prescribes that the first element
of L is either 0 or K. This would result in
the following behaviour:
| ?- _L = [A,B,C], domain(_L, 0, 3), firstpos(_L, 2).
A in{0}\/{2},
B in 0..3,
C in 0..3 ? ;
no
It would be nice to make this pruning work for all initial elements of a
list, in the following sense: if all elements before an
element X become 0, then this pruning should be applied
to X:
| ?- _L = [A,B,C], domain(_L, 0, 3), firstpos(_L, 2), A=0.
A = 0,
B in{0}\/{2},
C in 0..3 ? ;
no
The problem with this approach is that, if you write a recursive definition
for firstpos/2, you are forced to
use a constraint variable instead of the constant K in the
recursive call, because
the first positive element of the tail is not necessarily the same as that of
the whole list:
firstpos([H|T], K) :-
...
... #=> K1 #= K,
firstpos(T, K1).
...
To overcome this problem I suggest an alternative approach, using
the reified form of firstpos as a helper predicate:
% firstpos(+L, +K, ?B): B is 1 if, and only if
the first positive number in list L is K.
(B is a Boolean, i.e. 0..1 valued variable)
So keep passing the integer K the first positive element
should be equal to, and maintain a boolean variable B which
prescribes whether the first positive element should be K.
You can then add a reified constraint in the recursion, that
whenever B is 1, then the first element of the list has to be
either 0 or K.
Please send an email if you need
further clarification or help.
Last modified by Péter Szeredi,
szeredi@cs.bme.hu,
on 11.12.2024.