
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.DepthFirstSearch
public class DepthFirstSearch
DepthFirstSearch class (DFS). A blind search algorithm.
Expands deepest nodes first.
DFS is neither complete nor optimal, and has a time complexity of O(∞) and a space complexity of O(b*d). However if the problem's expand function returns the same node only once to prevent DFS from ending in a cycle (by keeping track of the nodes that were already visited) and if the state space is finite, DFS can be made complete.
Implementation data structure is a Stack (LIFO).
Backtracking
,
Serialized FormNested Class Summary  

static class 
DepthFirstSearch.OptionIterator
An iterator over a state space in depthfirst order. 
Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate 

AlgorithmicTemplate.Configuration 
Constructor Summary  

DepthFirstSearch()

Method Summary  

Function 
complexity()
O(∞). 
protected java.util.Iterator 
createTraversal(GeneralSearchProblem problem)
Define a traversal order by creating an iterator for the problem's state space. 
boolean 
isOptimal()
Whether this search algorithm is optimal. 
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, solveImpl 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Constructor Detail 

public DepthFirstSearch()
Method Detail 

public Function complexity()
AlgorithmicTemplate.solve(AlgorithmicProblem)
public Function spaceComplexity()
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 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 