## 4.1 Basic Search Engines

All these engines take a script as input and return a list of its solutions.

`base.one`

`{Search.base.one ``+ScriptP`` ``?Xs``}`

returns a singleton list containing the first solution of the script `+ScriptP` (a unary procedure) obtained by depth-first search. If no solution exists, `nil` is returned.

As an example,

`{Search.base.one proc {\$ X}                    choice                         choice X=ape [] X=bear end                      [] X=cat                      end                  end}`

returns the list `[ape]`.

`base.all`

`{Search.base.all ``+ScriptP`` ``?Xs``}`

returns the list of all solutions of the script `+ScriptP` (a unary procedure) obtained by depth-first serach. As an example,

`{Search.base.all proc {\$ X}                    choice                         choice X=ape [] X=bear end                      [] X=cat                      end                  end}`

returns the list `[ape bear cat]`.

`Search.base.best`

`{Search.base.best ``+ScriptP`` ``+OrderP`` ``?Xs``}`

returns a singleton list containing the best solution with respect to the order `+OrderP` (a binary procedure) of the script `+ScriptP` (a unary procedure) obtained by branch and bound search. If no solution does exist, `nil` 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 `+OrderP`. The binary procedure `+OrderP` 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.

For instance, the following script constrains its root variable to a pair of integers, such that a certain equation holds between its components.

`proc {Script Root}   X={FD.int 1#10} Y={FD.int 1#10}in    Y =: 10 - X - 2*Y   Root = X#Y   {FD.distribute split Root}end`

With the order

`proc {MaxSum Old New}   Old.1 + Old.2 <: New.1 + New.2end`

we can search for a solution with maximal sum of `X` and `Y` by

`{SearchBest Script MaxSum}`

This returns the singleton list `[7#1]`.

Similarly, we can search for the solution with the maximal product, by using the order:

`proc {MaxProduct Old New}   Old.1 * Old.2 <: New.1 * New.2end`

in:

`{SearchBest Script MaxProduct}`

This returns the singleton list `[4#2]`.

Denys Duchier, Leif Kornstaedt, Martin Homik, Tobias Müller, Christian Schulte and Peter Van Roy
Version 1.4.0 (20080702)