alice
library
manual.
signature SEARCH
structure Search : SEARCH
This section describes the search engines found in the structure Search.
Constraint problems have to be formulated as a script, a unary function taking as argument a computation space and posting the necessary constraints in this space. This script can then be passed to different search engines, which will return none, one or several solutions of the problem.
Scripts which create a large number of variables or propagators or scripts for which the search tree is very deep might use too much memory to be feasible. The search engines described in this section feature support for so-called recomputation. Recomputation reduces the space requirements for these scripts in that it trades space for time.
Search engines that do not use recomputation create a copy of a computation space in each distribution step. This copy is needed such that the engine is able to follow more than one alternative of a choice.
If, for instance, a single solution search engine finds a solution after 200 distribution steps (i. e. the search tree has a depth of 201), 200 copies are created and stored by the engine.
Recomputation reduces the number of copies needed: Instead of creating a copy in each distribution step, only every n-th distribution step a copy is created. A space for which no copy has been created can be recomputed from a copy located higher above in the search tree by recomputing some distribution steps. In the worst case, n-1 distribution steps have to be recomputed. The parameter n is the so-called recomputation distance.
The following search engines take the recomputation distance as an argument (it is denoted by rcd). A value of 2 for rcd means that only each second distribution step a copy is created. The value 1 for rcd means that in each distrbution step a copy is created, that is no recomputation is used. Values less than 1 mean that none but an initial copy is created: from this initial copy all other spaces are recomputed.
Recomputation can also reduce both space and time requirements. Searching a single solution of a script which features a good heuristic (i. e. there are only very few failures) creates copies which are not used. Recomputation avoids this, resulting in improvement with respect to both space and time.
To get an idea on how search engines are programmed in Alice, take a look at the example given here.
import signature SEARCH from "x-alice:/lib/gecode/SEARCH-sig"
import structure Search from "x-alice:/lib/gecode/Search"
signature SEARCH =
sig
val searchOne : (Space.space -> 'a) -> (Space.space * 'a) option
val searchAll : (Space.space -> 'a) -> Space.space list * 'a
val searchBest :
(Space.space -> 'a * (Space.space * Space.space -> unit)) ->
(Space.space * 'a) option
structure Recompute : sig
val searchOne : (Space.space -> 'a) * int -> (Space.space * 'a) option
val searchAll : (Space.space -> 'a) * int -> Space.space list * 'a
end
end
returns the first solution of script obtained by depth-first search. If no solution exists, NONE is returned.
returns the list of all solutions of script obtained by depth-first search.
returns the best solution of script obtained by depth-first branch and bound search. If no solution exists, NONE is returned. better takes the current space and the space of the previous solution and posts constraints that ensure that the current space has to yield a better solution.
The search engines in the Recompute structure take the mrd (maximum recomputation distance) as an additional integer argument. Otherwise, they behave just like the search engines without recomputation.