alice
library
manual.

Alice Project

The Search structure


________ Synopsis ____________________________________________________

    signature SEARCH
    structure Search : SEARCH

This section describes the search engines found in the structure Search. All of these engines support recomputation, the possibility to stop their execution and various kinds of output.

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. A recomputation distance of n means that the space needed decreases by a factor of n and that the time needed increases by a factor of n.

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.

Recomputation requires that the distribution strategy used in the script be deterministic. Deterministic means that the created choices and their order are identical in repeated runs of the script. This is true for all strategies in the finite domain structure, but for example not for strategies with randomized components.

Each of the engines is provided with two different types of output. The first kind returns a list of solutions as the engines, whereas the second kind returns a list of succeeded spaces.

To get an idea on how search engines are programmed in Alice, take a look at the example given here.


________ Import ______________________________________________________

    import signature SEARCH from "x-alice:/lib/constraints/SEARCH-sig"
    import structure Search from "x-alice:/lib/constraints/Search"

________ Interface ___________________________________________________

signature SEARCH =
    sig
	type 'a order = 'a * 'a -> unit

	datatype 'a bound_solution =
	    BOUND_NONE
	  | BOUND_SOME of 'a
	  | BOUND_CUT

	val searchOne : (unit -> 'a) -> 'a option
	val searchOneDepth : (unit -> 'a) * int -> 'a option
	val searchOneDepthS : (unit -> 'a) * int -> 'a Space.space option
	val searchOneBound : (unit -> 'a) * int * int -> 'a bound_solution
	val searchOneBoundS : (unit -> 'a) * int * int -> 'a Space.space bound_solution
	val searchOneIter : (unit -> 'a) * int -> 'a option
	val searchOneIterS : (unit -> 'a) * int -> 'a Space.space option
	val searchOneLDS : (unit -> 'a) * int -> 'a option
	val searchOneLDSS : (unit -> 'a) * int -> 'a Space.space option

	val searchAll : (unit -> 'a) -> 'a list
	val searchAllDepth : (unit -> 'a) * int -> 'a list
	val searchAllDepthS : (unit -> 'a) * int -> 'a Space.space list

	val searchBest : (unit -> 'a) * 'a order -> 'a option
	val searchBestBAB : (unit -> 'a) * 'a order * int -> 'a option
	val searchBestBABS : (unit -> 'a) * 'a order * int -> 'a Space.space option
	val searchBestRestart : (unit -> 'a) * 'a order * int -> 'a option
	val searchBestRestartS : (unit -> 'a) * 'a order * int -> 'a Space.space option
    end

________ Description _________________________________________________

type 'a order = 'a * 'a -> unit

This type denotes the order used for branch and bound and best solution search.

searchOne script

returns the first solution of script obtained by depth-first search. If no solution exists, NONE is returned.

searchOneDepth (script,rcd)

returns the first solution of script obtained by depth-first search with recomputation distance rcd. If no solution exists, NONE is returned.

searchOneDepthS (script,rcd)

returns the first succeeded space of script obtained by depth-first search with recomputation distance rcd. If no solution exists, NONE is returned.

searchOneBound (script,bound,rcd)

returns the first solution of script obtained by depth-first search with recomputation distance rcd, where the depth of the search tree explored is less than or equal to bound.

If there is no solution in a depth less than or equal to bound, but there might be solutions deeper in the tree, BOUND_CUT is returned. In case the entire search tree has a depth less than bound and no solution exists, BOUND_NONE is returned.

searchOneBoundS (script,bound,rcd)

returns the first succeeded space of script obtained by depth-first search with recomputation distance rcd, where the depth of the search tree explored is less than or equal to bound.

If there is no solution in a depth less than or equal to bound, but there might be solutions deeper in the tree, CUT is returned. In case the entire search tree has a depth less than bound and no solution exists, NONE is returned.

searchOneIter (script,rcd)

returns the first solution of script obtained by iterative deepening depth-first search with recomputation distance rcd. If no solution exists, NONE is returned.

searchOneIterS (script,rcd)

returns the first succeeded space of script obtained by iterative deepening depth-first search with recomputation distance rcd. If no solution exists, NONE is returned.

searchOneLDS (script,m)

returns the first solution of script obtained by limited discrepancy search allowing m discrepancies. If no solution exists, NONE is returned.

Typically, distribution strategies follow a heuristics that has been carefully designed to suggest most often "good" alternatives leading to a solution. This is taken into account by limited discrepancy search (LDS).

Exploring against the heuristic is called a discrepancy. LDS explores the search tree with no allowed discrepancy first, then allowing 1,2,... discrepancies until a solution is found, or a given limit for the discrepancies is reached.

Additionally, LDS makes a discrepancy first at the root of the search tree. This takes into account that it is more likely for a heuristic to make a wrong decision near the root of a tree where only little information is available. If no solution is found, discrepancies are made further down in the tree.

searchOneLDSS (script,m)

returns the first succeeded space containing the solution of script obtained by limited discrepancy search allowing m discrepancies. If no solution exists, NONE is returned.

Typically, distribution strategies follow a heuristics that has been carefully desgined to suggest most often "good" alternatives leading to a solution. This is taken into account by limited discrepancy search (LDS).

Exploring against the heuristic ist called a discrepancy. LDS explores the search tree with no allowed discrepancy first, then allowing 1,2,... discrepancies until a solution is found, or a given limit for the discrepancies is reached.

Additionally, LDS makes a discrepancy first at the root of the search tree. This takes into account that it is more likely for a heuristic to make a wrong decision near the root of a tree where only little information is available. If no solution is found, discrepancies are made further down in the tree.

searchAll script

returns a list of all solutions of the script obtained by depth-first search. If no solution exists, the empty list is returned.

searchAllDepth (script,rcd)

returns a list of all solutions of the script obtained by depth-first search with recomputation distance rcd. If no solution exists, the empty list is returned.

searchAllDepthS (script,rcd)

returns a list of all succeeded spaces of the script obtained by depth-first search with recomputation distance rcd. If no solution exists, the empty list is returned.

searchBest (script,order)

returns the best solution with respect to a order of script. If no solutions exists, NONE is returned.

searchBestBAB (script,order,rcd)

returns the best solution with respect to a order of script obtained by branch and bound search with recomputation distance rcd. If no solutions exists, NONE is returned.

The branch and bound strategy works as follows. When a solution is found, all the remaining alternatives are constrained to be better with respect to the order. The binary function order is applied with its first argument being the previous solution, and its second argument the root variable of a space for one of the remaining alternatives.

searchBestBABS (script,order,rcd)

returns the succeed space containing the best solution with respect to a order of script obtained by branch and bound search with recomputation distance rcd. If no solutions exists, NONE is returned.

The branch and bound strategy works as follows. When a solution is found, all the remaining alternatives are constrained to be better with respect to the order. The binary function order is applied with its first argument being the previous solution, and its second argument the root variable of a space for one of the remaining alternatives.

searchBestRestart (script,order,rcd)

returns the best solution with respect to a order of script obtained by branch and bound search with recomputation distance rcd. If no solutions exists, NONE is returned.

The restart strategy works as follows. When a solution is found, search is restarted for script with the additional constraint stating that the solution must be better with respect to the order. The binary procedure order is applied with the previous solution as first argument, and the root variable of the script as its second argument.

searchBestRestartS (script,order,rcd)

returns the succeed space containing the best solution with respect to a order of script obtained by branch and bound search with recomputation distance rcd. If no solutions exists, NONE is returned.

The restart strategy works as follows. When a solution is found, search is restarted for script with the additional constraint stating that the solution must be better with respect to the order. The binary procedure order is applied with the previous solution as first argument, and the root variable of the script as its second argument.



last modified 1970/01/01 01:00