On 23.09.2006, at 17:25, Chris Rathman wrote:
As I recall his solver did correctly do a breadth-first search, but it
didn't return the solution list in the same order as condi. I started
to read Christian's book but it was about that time that I got
off-track and haven't seen my way clear to complete the project yet.
The Oz user can control/define two orthogonal aspects in order to
specify how a CSP is solved: the distribution (branching) of the search
tree and the exploration of that tree.
In case only an arbitrary single solution is required, the most
critical aspect is a suitable distribution strategy. In this case, a
basic exploration strategy such as depth-first search is sufficient.
More complex exploration strategies have been proposed which do not
require exploring the full search tree for finding a good or an optimal
solution according to a user-defined formal criterion (e.g. limited
discrepancy search, best-solution search, or A*-search -- all discussed
in Christians book).
As I said, the most critical aspect is often a suitable distribution
strategy (instead of the exploration strategy), as this aspect controls
the shape etc. of the search tree. Constraint distribution is explained
in the Oz documentation (e.g. the tutorial
http://www.mozart-oz.org/documentation/fdt/index.html, in CTM, and of
course in detail in Christina's book).
Nevertheless, it may help to see the definition of a short but general
distributor in order to understand how distribution works. Essentially,
distribution strategies differ in two aspects: (i) in which order are
variables visited and (ii) which domain value is selected by the
distribution strategy. The simple example distributor MyDistributor
(see below) expects two functions which control these two aspects
(MyDistributor is a greatly simplified and not necessarily most
efficient version of FD.distribution -- the variables are traversed
twice: once when filtered and then again when selecting the variable to
distribute). The procedure MyDistributor expects as arguments the order
specification Ord and value specification Val, together with a list Xs
containing all variables in the CSP. MyDistributor waits until its
hosting space is stable. It then filters out already determined
variables. In case there are no undetermined variables left (i.e.Vars
is nil and the CSP is solved) the distributor does nothing. Otherwise,
the variable to distribute is selected (Order is a higher-order
function – a relative of Sort – which returns the list element fitting
best the given ordering function), bound to Var, and a domain
specification Dom is computed for this variable. The binary choice
states that the domain of Var is either Dom or its complement. These
two alternative constraints are added to the two child spaces (which
are created by the choice statement). The recursive call of
MyDistributor adapts the distribution for these child spaces to the
reduced list of variables (once filtered out, variables will never be
considered for distribution again).
proc {MyDistributor unit(order:Ord value:Val) Xs}
{Space.waitStable}
local
Vars={Filter Xs fun {$ X} {FD.reflect.size X} > 1 end}
in
if Vars \= nil
then
Var = {Order Vars Ord}
Dom = {Val Var}
in
choice {FD.int Dom Var} [] {FD.int compl(Dom) Var} end
{MyDistributor unit(order:Ord value:Val) Vars}
end
end
end
Hope this helps.
Best,
Torsten
--
Torsten Anders
Sonic Arts Research Centre • Queen's University Belfast
Frankstr. 49 • D-50996 Köln
Tel: +49-221-3980750
http://www.torsten-anders.de
http://strasheela.sourceforge.net
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
