|
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 |