
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 orbital.algorithm.template.GeneralBoundingSearch orbital.algorithm.template.IterativeBroadening
public class IterativeBroadening
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.
PackageUtilities#restrictTop(int,GeneralSearchProblem,Function)
,
Serialized FormIterativeDeepening
Nested Class Summary  

class 
IterativeBroadening.OptionIterator
An iterator over a state space in depthfirst 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 Onotation. 
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 

public IterativeBroadening()
Method Detail 

public Function getEvaluation()
EvaluativeAlgorithm
Also called objective function.
public Function complexity()
AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
public boolean isOptimal()
GeneralSearch
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.
isOptimal
in class GeneralSearch
protected final boolean isOutOfBounds(java.lang.Object node)
GeneralBoundingSearch
Called to check whether to prune a node. This implementation checks whether f(n) > bound. Overwrite to get additional behaviour.
isOutOfBounds
in class GeneralBoundingSearch
node
 the node to check.
GeneralBoundingSearch.getBound()
,
Template Methodprotected java.lang.Object solveImpl(GeneralSearchProblem problem)
solveImpl
in class GeneralSearch
GeneralSearch.search(Iterator)
.GeneralSearch.search(Iterator)
protected java.util.Iterator createTraversal(GeneralSearchProblem problem)
GeneralSearch
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
public Function spaceComplexity()
AlgorithmicTemplate.solve(AlgorithmicProblem)

Orbital library 1.3.0: 11 Apr 2009 

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