Russ Abbott wrote:
<snip>
The thread bomb approach generates a thread that is triggered when any of
the variables it is watching gets a value. This does not eliminate generate
and test, but since in effect all constraints are tested all the time it
does cut off the search immediately whenever any constraint is violated.
The argument for direct constraint programming is that it skips the generate
step. But when one's domain is a simple set the work done to eliminate the
generate step is essentially the same as the work done to test the value
once it is generated. The two are equivalent.
Expressing constraints in separate threads essentially guarantees that the
constraint are checked as early as possible, which is the same as removing
elements from the domain for domains that are sets.
<snip>
With the thread bomb approach constraints are actualy not checked as
soon as possible. So the search is not "cut off
immediately whenever any constraint is violated". Here is a simple example:
local A B in
A::50#99
B::0#49
A<:B
end
Feed this to Oz and you will immediately see a failure. Without any search. In
contrast, with the thread bomb approach, you have to generate 50^2 pairs of
values which you assign to A and B in order to check this constraint is not
satisfied.
Such propagators can be implemented in Oz by using built-in reflection,
watching and basic tells:
Use something along these lines:
proc {Less A B}
A<:{FD.reflect.min B}
B>:{FD.reflect.max A}
end
Then create a thread which calls it whenever the upperbound of A or lower bound
of B changes.
This is done with FD.watch.min and FD.watch.max.
Hope this clarifies the point.
--
Grégoire
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
