alice
library
manual.

The `MkSearch` functor

^Synopsis^{____________________________________________}

    signature SEARCH
    functor MkSearch (Problem : PROBLEM where type space = Space.space) 
                  :> SEARCH where type solution = Problem.solution
		            where type space    = Space.space

The MkSearch functor expects a description of the constraint problem to solve, given as a structure PROBLEM. It returns a structure that can be used for searching one or many solutions.

Have a look at the examples.

^Import^{______________________________________________}

    import signature SEARCH   from "x-alice:/lib/gecode/search-factory/SEARCH-sig"
    import structure MkSearch from "x-alice:/lib/gecode/search-factory/MkSearch"

^Interface^{___________________________________________}

signature SEARCH =
sig

  type solution
  type space

  exception NotAssigned
    
  val init              : solution Path.t -> unit
  val nextSolved        : unit -> (space * solution Path.t) option
  val isFinished        : unit -> bool
  val getOneSolution    : unit -> (solution * solution Path.t) option
  val getAllSolutions   : unit -> solution list
  val getUnexploredPath : unit -> solution Path.t option
  val stopSearch        : unit -> unit
  val betterThan        : solution -> unit

end

^Description^{_________________________________________}

type solution: The type of solutions. The MkSearch functor returns a type solution equal to Problem.solution.
type space: The type of constraint spaces. The MkSearch functor returns a type space equal to Space.space.
exception NotAssigned: Raised when the constraint problem to solve is under-specified, that is, a space is solved, but the variables necessary to read the solutions are not all determined. See the same exception in FD.
init path: Optional. Sets the top node of the search (by default it is the root node of the search tree). Raise Fail if the search has already begun and is not finished yet.
nextSolved (): Returns NONE if no more solution can be found. Otherwise, returns a pair (space, path) of the solved space and the path of this solution in the search tree.
isFinished (): Indicates if the search is finished.
getOneSolution (): Returns NONE if no more solution can be found. Otherwise, returns a pair (sol, path) of one new solution and the path of this solution in the search tree. Raises NotAssigned if the variables are not assigned in the solved space.
getAllSolutions (): Returns a list of all the (remaining) solutions. In the case of Branch & Bound, the first solution of the list (head of the list) is the best solution. Raises NotAssigned if the variables are not assigned in the solved space.
getUnexploredPath (): Returns the path corresponding to some unexplored node, usually the highest available in the tree. Returns NONE if one or less such nodes are available. Returns SOME path otherwise. The returned path is removed from the list of unexplored nodes so that it will not be explored in the future. Thread-safe.
stopSearch (): Stops the search. Thread-safe.
betterThan solution: Optional. In case of Branch & Bound search, constrain the search tree by inserting a new solution found in another place (like in distributed search). In general, you need not call this function when doing Branch & Bound search. Thread-safe.

last modified 2007/Mar/30 17:10

alice library manual.

The MkSearch functor

________ Synopsis ____________________________________________________

________ Import ______________________________________________________