orbital.algorithm.template
Class GeneralBoundingSearch

java.lang.Object
  orbital.algorithm.template.GeneralSearch
      orbital.algorithm.template.GeneralBoundingSearch

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm

Direct Known Subclasses:

BranchAndBound, IterativeBroadening, IterativeDeepening, IterativeDeepeningAStar

public abstract class GeneralBoundingSearch
extends GeneralSearch
implements EvaluativeAlgorithm

Abstract general bounding search scheme.

A general search that only executes up to a specified bound (which might as well vary during search).

Author:

André Platzer

See Also:

Serialized Form

Structure:

refines GeneralSearch, extends GeneralSearch

Nested Class Summary

Nested classes/interfaces inherited from class orbital.algorithm.template.GeneralSearch

GeneralSearch.OptionIterator

Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm

EvaluativeAlgorithm.EvaluationComparator

Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate

AlgorithmicTemplate.Configuration

Constructor Summary

GeneralBoundingSearch()

Method Summary

protected Real	getBound() Get the current bound.
protected boolean	isContinuedWhenFound() Whether the search is continued after a solution is found.
protected boolean	isOutOfBounds(java.lang.Object node) Whether a node is out of bounds.
protected java.lang.Object	processSolution(java.lang.Object node) Process a solution.
protected java.lang.Object	search(java.util.Iterator nodes) Run the general search algorithm scheme.
protected void	setBound(double bound) Deprecated. Since Orbital1.1 use setBound(Real) instead.
protected void	setBound(Real bound) Set the current bound.
protected void	setContinuedWhenFound(boolean continuedWhenFound) Set whether the search should continue after a solution is found.

Methods inherited from class orbital.algorithm.template.GeneralSearch

createTraversal, getProblem, isOptimal, solve, solveImpl

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

getEvaluation

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

complexity, solve, spaceComplexity

Constructor Detail

GeneralBoundingSearch

public GeneralBoundingSearch()

Method Detail

getBound

protected Real getBound()

Get the current bound. The search will only execute up to the specified bound (which might as well vary during search).

Returns:

the current bound beyond which search will not continue.

See Also:

isOutOfBounds(Object)

setBound

protected void setBound(Real bound)

Set the current bound.

setBound

protected void setBound(double bound)

Deprecated. Since Orbital1.1 use setBound(Real) instead.

isContinuedWhenFound

protected boolean isContinuedWhenFound()

Whether the search is continued after a solution is found.

Returns:

whether to continue searching for even better solutions when a solution has already been found.

setContinuedWhenFound

protected void setContinuedWhenFound(boolean continuedWhenFound)

Set whether the search should continue after a solution is found.

Parameters:

continueWhenFound - whether to continue searching for even better solutions when a solution is already found. Subclasses should set it to false if they are assuming that the first solution found is already the best one, which cannot be guaranteed for all algorithms. Set to true if the search should continue (perhaps after bounding) to find even better solutions.

processSolution

protected java.lang.Object processSolution(java.lang.Object node)

Process a solution.

The default implementation simply returns the solution node description. Overwrite to get more sophisticated behaviour.

Parameters:

node - the node describing the solution.

Returns:

the solution after processing it.

See Also:

Template Method

Preconditions:

getProblem().isSolution(node)

isOutOfBounds

protected boolean isOutOfBounds(java.lang.Object node)

Whether a node is out of bounds.

Called to check whether to prune a node. This implementation checks whether f(n) > bound. Overwrite to get additional behaviour.

Parameters:

node - the node to check.

Returns:

whether the node is out of current bounds.

See Also:

getBound(), Template Method

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.

Overrides:

search in class GeneralSearch

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