<< Prev | - Up - | Next >> |
In this section it is shown how Oz supports distribution with constraints. The following procedure creates binary choice-points for variables. The choice is delayed until propagation has reached a fixed point. Assume Dv
to be a vector of finite domain integers. The distribution differs in the order of the choice-points and in the constraint with which is distributed. Essentially, it works as follows
Select an element D
of Dv
which is not determined.
Select a value or a domain specification Spec
in the current domain of D
.
Create a choice point for X::Spec
and X::compl(Spec)
.
If not all elements of Dv
are determined, go to step 1.
The order of Dv
is preserved.
distribute
{FD.distribute
+Dist
+Xv
}
The vector Xv
is distributed according to the specification Dist
. Dist
may be either the atom naive
, ff
(for first-fail), split
or a record with label generic
:
naive
: Xv
must be a vector of finite domain integers. Considers only non-determined elements of Xv
. Chooses the leftmost variable X
in Xv
. Creates a choice point for X=L
and X\=:L
, where L
is the lower bound of the domain of X
.
ff
: Xv
must be a vector of finite domain integers. Considers only non-determined elements of Xv
. Chooses the leftmost variable X
in Xv
, whose domain size is minimal. Creates a choice point for X=L
and X\=:L
, where L
is the lower bound of the domain of X
.
split
: Xv
must be a vector of finite domain integers. Considers only non-determined elements of Xv
. Chooses the leftmost variable X
in Xv
, whose domain size is minimal. Creates a choice point for X=<:M
and X>:M
, where M
is the middle of the domain of X
(see FD.reflect.mid
).
generic(order:
+Order
<= size
filter:+Filter
<= undet
select:+Select
<= id
value:+Value
<= min
procedure:+Proc
<= proc {$} skip end)
Considers only those elements in Xv
, for which Filter
is true. Chooses the leftmost element, which is minimal with respect to Order
and selects the corresponding variable D
by Select
. Creates a choice point for D::Spec
and D::compl(Spec)
, where Spec
is selected by Value
.
The values under the respective features must be as follows:
Order
:
Binary boolean function P
: Selects the leftmost element in Xv
which is minimal with respect to the order relation P
.
naive
: Selects the leftmost variable.
size
: Selects the leftmost variable, whose domain is minimal.
min
: Selects the leftmost variable, whose lower bound is minimal.
max
: Selects the leftmost variable, whose upper bound is maximal.
nbSusps
: Selects the variable with the largest number of suspensions. If several variables suspend on the maximal number of constraints, the leftmost variable whose domain is minimal is selected.
Filter
:
Unary boolean function P
: Considers only the elements X
in Xv
, for which {P X}
yields true
.
undet
: Considers only undetermined variables.
Select
:
Unary function P
: Selects the variable to enumerate from the selected element by Order
and Filter
.
id
: The variable to enumerate is the selected element.
Value
:
Binary procedure P
: Takes a variable as first argument, and binds its second argument to a domain descriptor D
to serve as the restriction on said variable to be used in a binary distribution step (D
in one branch, compl(D)
in the other).
min
: Selects the lower bound of the domain.
max
: Selects the upper bound of the domain.
mid
: Selects the element, which is closest to the middle of the domain (the arithmetical means between the lower and upper bound of the domain). In case of ties, the smaller element is selected.
splitMin
: Selects the interval from the lower bound to the middle of the domain (see mid
).
splitMax
: Selects the interval from the element following the middle to the upper bound of the domain (see mid
).
Proc
: Is applied when stability is reached. Since this application may cause instability, distribution is continued when stability is reached again.
Note, that in case Det
is det
or in case Order
is size
, lower
, upper
, or nbSusps
, the elements of Xv
must be finite domain integers.
For example, {FD.distribute ff Dv}
can be expressed as
{FD.distribute generic Dv},
{FD.distribute split Dv}
as
{FD.distribute generic(value: splitMin) Dv},
and {FD.distribute naive Dv}
as
{FD.distribute generic(order: naive) Dv}
The naive distribution can also be defined as follows using the value
feature.
{FD.distribute
generic(value: fun {$ D}
{FD.reflect.min D}
end) Ds}
choose
{FD.choose
+Dist
+Xv
?X
?Spec
}
Chooses the element X
in Xv
according to the description Dist
. A specification Spec
for the element X
is returned according to the description Dist
. The parameter Dist
is defined in the same way as for FD.distribute
except for the value selection. If the feature value
is used for generic distribution, the field must be constrained to a unary function P
which selects a value from the domain of the selected variable (see below for an example). For example,
{FD.choose ff Xs E S}
selects the element E
in the list Xs
according to the first-fail strategy and binds S
to the current lower bound of E
.
{FD.choose generic(value:splitMin) Xv E S}
selects the element E
in the list Xs
according to the first-fail strategy and binds S
to the pair 0#M
, where M
is the result of {FD.reflect.mid E}
. For the naive distribution strategy, the following may be used.
{FD.choose generic(value: fun{$ X}
{FD.reflect.min X}
end)
Xv E S}
<< Prev | - Up - | Next >> |