
Orbital library  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object orbital.algorithm.template.GeneralSearch
public abstract class GeneralSearch
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.
GeneralSearchProblem
,
Hector Geffner. Modelling and Problem Solving,
Strategy,
Table of Algorithms in Comparison,
Serialized FormNested 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 

public GeneralSearch()
Method Detail 

protected final GeneralSearchProblem getProblem()
null
if there is no current problem (since solve has not yet been called etc.).public abstract boolean isOptimal()
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.
public final java.lang.Object solve(AlgorithmicProblem gp)
This method does not need to be overwritten.
Overwrite solveImpl(GeneralSearchProblem)
, instead.
solve
in interface AlgorithmicTemplate
gp
 algorithmic problem hook class which must fit the concrete
algorithmic template framework implementation.
null
if no solution was found at all.solveImpl(GeneralSearchProblem)
protected java.lang.Object solveImpl(GeneralSearchProblem problem)
Like the default solution policies, this implementation will
createTraversal(GeneralSearchProblem)
.
search(Iterator)
to search through the state space in the traversal order.
search(Iterator)
.search(Iterator)
protected abstract java.util.Iterator createTraversal(GeneralSearchProblem problem)
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.
problem
 the problem whose state space to create a traversal iterator for.
GeneralSearch.OptionIterator
protected java.lang.Object search(java.util.Iterator nodes)
This method only needs to be overwritten to provide a completely different search scheme. Usually, the default search algorithm scheme is sufficient.
nodes
 is the iterator over the nodes to visit (sometimes called open set)
which determines the traversal order.

Orbital library 1.3.0: 11 Apr 2009 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 