Orbital library

orbital.algorithm.template
Class GeneralSearch

java.lang.Object
  extended by orbital.algorithm.template.GeneralSearch
All Implemented Interfaces:
java.io.Serializable, AlgorithmicTemplate
Direct Known Subclasses:
BestFirstSearch, BreadthFirstSearch, DepthFirstSearch, GeneralBoundingSearch, IterativeExpansion, LocalOptimizerSearch

public abstract class GeneralSearch
extends java.lang.Object
implements AlgorithmicTemplate, java.io.Serializable

Abstract general search algorithm scheme.

The various subclasses implement different search strategies, but follow this coherent framework.

Apart from the reference to the problem to solve, GeneralSearch implementations are usually stateless.

Author:
André Platzer
See Also:
GeneralSearchProblem, Hector Geffner. Modelling and Problem Solving, Strategy, Table of Algorithms in Comparison, Serialized Form

Nested Class Summary
static class GeneralSearch.OptionIterator
          Abstract implementation base class for iterators determining the traversal order.
 
Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate
AlgorithmicTemplate.Configuration
 
Constructor Summary
GeneralSearch()
           
 
Method Summary
protected abstract  java.util.Iterator createTraversal(GeneralSearchProblem problem)
          Define a traversal order by creating an iterator for the problem's state space.
protected  GeneralSearchProblem getProblem()
          Get the current problem.
abstract  boolean isOptimal()
          Whether this search algorithm is optimal.
protected  java.lang.Object search(java.util.Iterator nodes)
          Run the general search algorithm scheme.
 java.lang.Object solve(AlgorithmicProblem gp)
          Solves a general search problem.
protected  java.lang.Object solveImpl(GeneralSearchProblem problem)
          Implements the solution policy.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate
complexity, spaceComplexity
 

Constructor Detail

GeneralSearch

public GeneralSearch()
Method Detail

getProblem

protected final GeneralSearchProblem getProblem()
Get the current problem.

Returns:
the problem specified in the last call to solve, or null if there is no current problem (since solve has not yet been called etc.).
Preconditions:
true

isOptimal

public abstract boolean isOptimal()
Whether this search algorithm is optimal.

If a search algorithm is not optimal, i.e. it might be content with solutions that are sub optimal only, then it can at most reliably find solutions, not best solutions. However, those solutions found still provide an upper bound to the optimal solution.

Returns:
whether this search algorithm is optimal, i.e. whether solutions found are guaranteed to be optimal.
Preconditions:
true
Postconditions:
RES == OLD(RES) && OLD(this) == this

solve

public final java.lang.Object solve(AlgorithmicProblem gp)
Solves a general search problem.

This method does not need to be overwritten. Overwrite solveImpl(GeneralSearchProblem), instead.

Specified by:
solve in interface AlgorithmicTemplate
Parameters:
gp - algorithmic problem hook class which must fit the concrete algorithmic template framework implementation.
Returns:
the solution found (represented as an option with solution state, final action and accumulated cost), or null if no solution was found at all.
See Also:
Template Method, solveImpl(GeneralSearchProblem)
Preconditions:
true
Postconditions:
solution == null ∨ p.isSolution(solution)

solveImpl

protected java.lang.Object solveImpl(GeneralSearchProblem problem)
Implements the solution policy.

Like the default solution policies, this implementation will

  1. Fetch a traversal order policy by calling createTraversal(GeneralSearchProblem).
  2. Then call search(Iterator) to search through the state space in the traversal order.
However, sophisticated search algorithms may want to change that policy and iterate the above process, resulting in a sequence of calls to those methods. They may do so by by overwriting this method.

Returns:
the solution found by search(Iterator).
See Also:
search(Iterator)
Preconditions:
problem == getProblem()
Postconditions:
solution == null ∨ p.isSolution(solution)

createTraversal

protected abstract java.util.Iterator createTraversal(GeneralSearchProblem problem)
Define a traversal order by creating an iterator for the problem's state space.

Lays a linear order through the state space which the search can simply follow sequentially. Thus a traversal policy effectively reduces a search problem through a graph to a search problem through a linear sequence of states. Of course, the mere notion of a traversal policy does not yet solve the task of finding a good order of states, but only encapsulate it. Complete search algorithms result from traversal policies that have a linear sequence through the whole state space.

Parameters:
problem - the problem whose state space to create a traversal iterator for.
Returns:
an iterator over the options of the problem's state space thereby encapsulating and hiding the traversal order.
See Also:
Factory Method, GeneralSearch.OptionIterator
Attributes:
secret traversal order

search

protected java.lang.Object search(java.util.Iterator nodes)
Run the general search algorithm scheme.

This method only needs to be overwritten to provide a completely different search scheme. Usually, the default search algorithm scheme is sufficient.

Parameters:
nodes - is the iterator over the nodes to visit (sometimes called open set) which determines the traversal order.
Returns:
the solution found searching the state space via nodes.
See Also:
Template Method
Postconditions:
solution == null ∨ p.isSolution(solution)

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.