orbital.algorithm.template
Class IterativeBroadening

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

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm

public class IterativeBroadening
extends GeneralBoundingSearch

Iterative Broadening (IB). A blind search algorithm.

Iterative Broadening uses increasing bounds for the breadth of the search space that is subject to expansion.

This algorithm is often inferior to iterative deepening, but may be useful for search graphs that are not locally finite.

Author:

André Platzer

See Also:

PackageUtilities#restrictTop(int,GeneralSearchProblem,Function), Serialized Form

Attributes:

usually inferior to IterativeDeepening

Nested Class Summary

class

IterativeBroadening.OptionIterator An iterator over a state space in depth-first order respecting the current bounds for the breadth of the search space that is subject to expansion.

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

IterativeBroadening()

Method Summary

Function	complexity() Measure for the asymptotic time complexity of the central solution operation in O-notation.
protected java.util.Iterator	createTraversal(GeneralSearchProblem problem) Define a traversal order by creating an iterator for the problem's state space.
Function	getEvaluation() Get the evaluation function used while processing.
boolean	isOptimal() Whether this search algorithm is optimal.
protected boolean	isOutOfBounds(java.lang.Object node) Whether a node is out of bounds.
protected java.lang.Object	solveImpl(GeneralSearchProblem problem) Solve with bounds 1, 3, 4, 5, ...
Function	spaceComplexity() O(b*d) where b is the branching factor and d the solution depth.

Methods inherited from class orbital.algorithm.template.GeneralBoundingSearch

getBound, isContinuedWhenFound, processSolution, search, setBound, setBound, setContinuedWhenFound

Methods inherited from class orbital.algorithm.template.GeneralSearch

getProblem, solve

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

solve

Constructor Detail

IterativeBroadening

public IterativeBroadening()

Method Detail

getEvaluation

public Function getEvaluation()

Description copied from interface: EvaluativeAlgorithm

Get the evaluation function used while processing.

Also called objective function.

Returns:

the evaluation function f:S→R used to evaluate (either utility or cost) value of states.

complexity

public Function complexity()

Description copied from interface: AlgorithmicTemplate

Measure for the asymptotic time complexity of the central solution operation in O-notation.

Returns:

the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

isOptimal

public boolean isOptimal()

Description copied from class: GeneralSearch

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.

Specified by:

isOptimal in class GeneralSearch

Returns:

whether this search algorithm is optimal, i.e. whether solutions found are guaranteed to be optimal.

isOutOfBounds

protected final boolean isOutOfBounds(java.lang.Object node)

Description copied from class: GeneralBoundingSearch

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.

Overrides:

isOutOfBounds in class GeneralBoundingSearch

Parameters:

node - the node to check.

Returns:

whether the node is out of current bounds.

See Also:

GeneralBoundingSearch.getBound(), Template Method

solveImpl

protected java.lang.Object solveImpl(GeneralSearchProblem problem)

Solve with bounds 1, 3, 4, 5, ... until a solution is found.

Overrides:

solveImpl in class GeneralSearch

Returns:

the solution found by GeneralSearch.search(Iterator).

See Also:

GeneralSearch.search(Iterator)

createTraversal

protected java.util.Iterator createTraversal(GeneralSearchProblem problem)

Description copied from class: GeneralSearch

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

spaceComplexity

public Function spaceComplexity()

O(b*d) where b is the branching factor and d the solution depth.

Returns:

the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)