orbital.algorithm.template
Class BestFirstSearch

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

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm

Direct Known Subclasses:

AStar

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.

Author:

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

EvaluativeAlgorithm.EvaluationComparator

Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate

AlgorithmicTemplate.Configuration

Constructor Summary

BestFirstSearch()

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

getEvaluation

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

complexity, solve, spaceComplexity

Constructor Detail

BestFirstSearch

public BestFirstSearch()

Method Detail

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