Search

  Search is supported on two levels of abstraction. Section describes procedures implementing various search strategies including depth-first, breadth-first one-solution search, different all-solution strategies and strategies for optimal solution search. In Section an object providing for a convenient front-end to search is described. It can be seen as a more powerful version of a Prolog toplevel: multiple solutions (and also previous ones) may be requested, the depth of the search may be bounded, and the search process itself may be stopped and resumed. For a more detailed treatment of search in Oz see Constraint Programming in Oz [9] . Besides of the search abstractions described here, DFKI Oz features a tool called Solver, which provides a higly convenient access to search. A brief introduction can be found in An Oz Primer [12] , a complete description in DFKI Oz User's Manual [8] .

The Search Module

    The module Search contains several predefined procedures implementing some common search strategies.

{SolveCombinator +P ?T}

    Provides access to the basic search mechanism of Kernel Oz. Spawns a local computation space in which the unary procedure P is applied to a fresh root variable. According to how reduction within this space proceeds, T might be bound as follows:

failed

The computation space has failed.

solved( P_1 )

The computation space has been solved, where P_1 is a unary procedure containing the abstracted solution. Further information on P_1 is available at its feature status: In case that the local computation space has been entailed its field is entailed, and stable otherwise.

distributed( P_1 P_2 )

The computation space has been distributed. P_1 includes the first alternative of the distributed disjunction in abstracted form, whereas P_2 includes the remaining alternatives. In case that the distributed disjunction held two alternatives, P_2 .status is last, otherwise it is more. In either case P_1 .status is last. Both P_1 and P_2 might be applied only once.

One Solution Search

   The submodule Search.one provides the following procedures for one solution search.

{one.depth +P ?T}

   Searches in depth-first fashion for a solution of the unary procedure P. If no solution exists, T is constrained to failed, otherwise to solved( P_1 ), where P_1 is a unary procedure containing the abstracted solution.

{one.breadth +P ?T}

   Searches in breadth-first fashion for a solution of the unary procedure P. If no solution exists, T is constrained to failed, otherwise to solved( P_1 ), where P_1 is a unary procedure containing the abstracted solution.

{one.bound +P +I ?T}

   Searches in depth-first fashion for a solution of the unary procedure P up to a depth of I in the search tree. If no solution exists within this depth, T is constrained to failed. Otherwise T is constrained to solved( P_1 ), where P_1 is a unary procedure containing the abstracted solution.

{one.iter +P +I ?T}

   Searches in iterative depth-first fashion for a solution of the unary procedure P. Search is performed iteratively: first a solution up to depth 1 in the search tree is searched for, then up to depth 2, 4, until either a solution is found or in depth 2^ I no solution is found. If no solution exists, T is constrained to failed, otherwise to solved( P_1 ), where P_1 is a unary procedure containing the abstracted solution.

All Solution Search

   The submodule Search.all provides for all-solution search strategies.

{all.eager +P ?Ts}

   Performs depth-first search for the unary procedure P, and collects all tuples of the form solved(S) to the list Ts, where S is a unary procedure containing the abstracted solution. This procedure is like bagof in Prolog.

{all.lazy +P Ts}

   Performs demand-driven depth-first search for the unary procedure P. Constraining Ts to a list will start the search. For example,

declare Ts in
{Search.all.lazy proc {$ A} 
                   or A=ape [] A=bear [] A=cat ro 
                end Ts}

does not start search. Feeding

declare T1 in Ts=T1|_

prompts for a first solution and constrains T1 to a unary solved-tuple containing the abstracted solution. This can be done repeatedly. For example

declare T2 T3 in Ts=_|T2|T3|_

constrains T2 and T3 as expected. Demanding a solution in the case that no further solution exists, results in constraining the corresponding tail of the list to [failed]. For example

declare T4 Tr in Ts=_|_|_|T4|Tr

constrains T4 to failed and Tr to nil. Instead of demanding a solution by constraining the list to _|_, the search can be terminated by constraining it to nil instead.

Best Solution Search

   Best solution search requires the notion of an ordering relation. If P is a binary procedure implementing an ordering relation, we say that Y is better than X, if { P X Y} holds. For the following procedures the respective ordering relations should be total and irreflexive. Totality ensures that a global optimum and not only a local optimum is searched for, whereas irreflexivity may lead to a much smaller search space.

{best.bab +P1 +P2 ?T}

   Applies depth-first search for an optimal solution to the unary procedure P1. Optimality is with respect to the ordering relation as specified by the binary procedure P2. A branch and bound strategy is used: once a solution is found, only solutions that are better with respect to P2 are searched for. With every better solution found, the constraints on further solutions are strengthened, thus pruning the search space.

{best.restart +P1 +P2 ?T}

   Applies depth-first search for an optimal solution to the unary procedure P1. Optimality is with respect to an ordering relation as specified by the binary procedure P2. Once a solution is found, the entire search is restarted with the original problem and the constraint that the solution has to be better with respect to the given order. This is applied iteratively until no better solution exists.

Displaying Solutions

For convenient access to the output of the search abstractions described above the following is provided.

{strip +X ?Ys}

    Ys is constrained to a list of solutions as described by X. Solutions in abstracted form are applied, X can have the form as produced by the search abstractions in the modules Search.one, Search.all, Search.best.

The Search Object

  The object Search provides for an interactive interface to search. When the system starts, it is alredy initialized (as explained below), and ready for use.  

init(query:  +QueryP  <= fun {$} 
                             'Solution comes from default query' 
                          end
     solved: +SolvedP <= Browse
     noNext: +NoNextP <= proc {$}  
                            {Browse 'no further solution.'} 
                         end
     noPrev: +NoPrevP <= proc {$} 
                            {Browse 'no previous solution.'} 
                         end
     depth:  +DepthI  <= ~1)

   Initializes the Search object. QueryP must be a unary procedure, giving the search problem to be solved. Additionally, the object takes three actions. The action specified by the field solved has to be a unary procedure to be applied to a solution found. The other actions as specified by noNext and noPrev are called whenever a next, respectively previous solution, is desired but does not exist. The parameter DepthI describes to which depth the search tree will be explored, a value of 1 is used for infinite depth.

action(solved: +SolvedP <= % as above
       noNext: +NoNextP <= % as above
       noPrev: +NoPrevP <= % as above\ozfont)

   Sets the actions as described in the init method for the Search object. If a field is left out, the according action remains unchanged. If the SolvedP action is specified, it is applied to the current solution.

query(+P <= % as above\ozfont)

    P, a unary procedure, is the problem to be solved. Any previous search is stopped and its further solutions are discarded.

depth(+I <= ~1)

   Sets the maximal depth, i.e. how deep the search tree will be explored. The integer 1 means unbounded depth.

next(+I <= 1)

   Demands the next I solutions, for each solution found the action as specified by the field solved will be applied to the solution. If there are less solutions than requested, the action specified by noNext will be invoked.

prev(+I <= 1)

   Demands the I previous solutions, for each solution found the action as specified by the field solved will be applied to the solution. If there are less solutions than requested, the action specified by noPrev will be invoked.

stop

   Interrupts the search process of the object. May be resumed by using next or prev.