Orbital library

Class BestFirstSearch

  extended by orbital.algorithm.template.GeneralSearch
      extended by orbital.algorithm.template.BestFirstSearch
All Implemented Interfaces:
java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm
Direct Known Subclasses:

public abstract class BestFirstSearch
extends GeneralSearch
implements EvaluativeAlgorithm

BestFirstSearch class (BFS). An heuristic search algorithm.

Expands best nodes first, i.e. those that have min f(n).

Implementation data structure is a Heap.

André Platzer
See Also:
Greedy, Serialized Form

Nested Class Summary
static class BestFirstSearch.OptionIterator
          An iterator over a state space in best-first order.
Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm
Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate
Constructor Summary
Method Summary
protected  java.util.Iterator createTraversal(GeneralSearchProblem problem)
          Define a traversal order by creating an iterator for the problem's state space.
Methods inherited from class orbital.algorithm.template.GeneralSearch
getProblem, isOptimal, search, solve, solveImpl
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.EvaluativeAlgorithm
Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate
complexity, solve, spaceComplexity

Constructor Detail


public BestFirstSearch()
Method Detail


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
problem - the problem whose state space to create a traversal iterator for.
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.