Orbital library

orbital.algorithm.template
Class BreadthFirstSearch

java.lang.Object
  extended by orbital.algorithm.template.GeneralSearch
      extended by orbital.algorithm.template.BreadthFirstSearch
All Implemented Interfaces:
java.io.Serializable, AlgorithmicTemplate

public class BreadthFirstSearch
extends GeneralSearch

BreadthFirstSearch class (BrFS). A blind search algorithm.

Expands shallowest nodes first.

BrFS is complete, optimal for uniform costs, and has a time and space complexity of O(bd).

Implementation data structure is a Queue (FIFO).

Author:
André Platzer
See Also:
Serialized Form
Note:
is a basic aspect of exploring the search space breadth-first.

Nested Class Summary
static class BreadthFirstSearch.OptionIterator
          An iterator over a state space in breadth-first order.
 
Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate
AlgorithmicTemplate.Configuration
 
Constructor Summary
BreadthFirstSearch()
           
 
Method Summary
 Function complexity()
          O(bd) 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.
 boolean isOptimal()
          Optimal only for when costs are uniform.
 Function spaceComplexity()
          O(bd) 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

BreadthFirstSearch

public BreadthFirstSearch()
Method Detail

complexity

public Function complexity()
O(bd) where b is the branching factor and d the solution depth. DepthFirstSearch might not find a solution for search space graphs with inifinite breadth. O((bd-1)/(b-1) + bd) more precisely.

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(bd) where b is the branching factor and d the solution depth. O(bd-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()
Optimal only for when costs are uniform. Costs are uniform if they fulfill h*(n)=0.

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

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.