orbital.algorithm.template
Class DepthFirstSearch

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

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate

public class DepthFirstSearch
extends GeneralSearch

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

Author:

André Platzer

See Also:

Backtracking, Serialized Form

Note:

is a basic aspect of exploring the search space depth-first.

Nested Class Summary

static class

DepthFirstSearch.OptionIterator An iterator over a state space in depth-first 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

DepthFirstSearch

public DepthFirstSearch()

Method Detail

complexity

public Function complexity()

O(∞). DepthFirstSearch might not find a solution for search space graphs with inifinite depth or infinite breadth. o(d+1) up to O((b^d+1-1)/(b-1)) more precisely. On average &asym;b^d/2.

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)

spaceComplexity

public Function spaceComplexity()

O(b*d) where b is the branching factor and d the solution depth. O((b-1)*d + 1) more precisely.

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)

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.

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.

Specified by:

createTraversal in class GeneralSearch

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