
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.IterativeExpansion
public class IterativeExpansion
Iterative Expansion (IE).
Iterative Expansion is a memorybounded search algorithm that combines the space complexity advantages of IDA^{*} with A^{*}'s ability of remembering more than just a bound from the rest of the search tree. IE is inferior to SMA^{*} which has a more flexible tradeoff between reducing memory consumption and remembering parts of the search tree in order to avoid reexpansion. However, IE has much less memory management overhead and thus has a comparable performance to that of SMA^{*}. Nevertheless, all current memorybounded algorithms have difficulties with problems having too many distinct fcosts (i.e. f(S) is large).
Nested Class Summary 

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

GeneralSearch.OptionIterator 
Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm 

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic 
Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm 

EvaluativeAlgorithm.EvaluationComparator 
Constructor Summary  

IterativeExpansion(Function heuristic)
Create a new instance of IDA^{*} search. 
Method Summary  

Function 
complexity()
O(b^{d}) where b is the branching factor and d the solution depth. 
protected java.util.Iterator 
createTraversal(GeneralSearchProblem problem)
Define a traversal order by creating an iterator for the problem's state space. 
Function 
getEvaluation()
f(n) = g(n) + h(n). 
Function 
getHeuristic()
Get the heuristic function used. 
boolean 
isOptimal()
Optimal if heuristic is admissible, and initial bound sufficiently large (usually ∞). 
void 
setHeuristic(Function heuristic)
Set the heuristic function to use. 
protected java.lang.Object 
solveImpl(GeneralSearchProblem problem)
Implements the solution policy. 
Function 
spaceComplexity()
O(b*d) where b is the branching factor and d the solution depth. 
Methods inherited from class orbital.algorithm.template.GeneralSearch 

getProblem, search, 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 IterativeExpansion(Function heuristic)
heuristic
 the heuristic cost function h:S→R embedded in the evaluation function f.getEvaluation()
Method Detail 

public Function getHeuristic()
HeuristicAlgorithm
getHeuristic
in interface HeuristicAlgorithm
public void setHeuristic(Function heuristic)
HeuristicAlgorithm
An heuristic cost function h:S→R is estimating the cost to get from a node n to a goal G. For several heuristic algorithms this heuristic function needs to be admissible
A heuristic cost function h is monotonic :⇔ the fcosts (with h) do not decrease in any path from the initial state ⇔ h obeys the triangular inequality
A simple improvement for heuristic functions is using pathmax.
setHeuristic
in interface HeuristicAlgorithm
heuristic
 the heuristic cost function h:S→R estimating h^{*}.
h will be embedded in the evaluation function f
.public Function getEvaluation()
getEvaluation
in interface EvaluativeAlgorithm
getEvaluation
in interface HeuristicAlgorithm
public Function spaceComplexity()
spaceComplexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
public Function complexity()
complexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
public boolean isOptimal()
isOptimal
in class GeneralSearch
protected java.lang.Object solveImpl(GeneralSearchProblem problem)
GeneralSearch
Like the default solution policies, this implementation will
GeneralSearch.createTraversal(GeneralSearchProblem)
.
GeneralSearch.search(Iterator)
to search through the state space in the traversal order.
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.
createTraversal
in class GeneralSearch
problem
 the problem whose state space to create a traversal iterator for.
GeneralSearch.OptionIterator

Orbital library 1.3.0: 11 Apr 2009 

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