orbital.algorithm.template
Class AStar

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

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, HeuristicAlgorithm

Direct Known Subclasses:

WAStar

public class AStar
extends BestFirstSearch
implements HeuristicAlgorithm

A^* search class.

In fact this is a special instance of WA^* with W=1.

A^* is complete, optimal if the heuristic function h is admissible. It has a time and space complexity of O(b^d). A^* is optimal in another sense ("optimally efficient"): no other algorithm expands less nodes than A^* with the same heuristic function. It also expands nodes only once. But this does not mean that it is always fastest. A^* expands less nodes with better heuristic functions (h' is better than h if 0 < h < h' ≤ h^*).

To be precise, like most (if not all) other search algorithms, A^* achieves completeness only on locally finite graphs (i.e. with finite branching factors) provided that the costs keep away from zero, i.e.

∃ε> 0 ∀s∈S∀a∈A(s) c(s,a) > ε

For the (admissible) heuristic h=0, A^* results in (non-uniform cost) BreadthFirstSearch, whilst no admissible heuristic can exist that will let A^* resemble DepthFirstSearch. For the ignorant cost function g=0, A^* degrades to a simple best first search that always selects best nodes first regardless of the history. This behaviour for g=0 resembles HillClimbing but is not limited to selecting from most recently expaned nodes, nevertheless with g=0 it is still incomplete and not optimal.

Author:

André Platzer

See Also:

"P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions of Systems Science and Cybernetics, 4:100-107, 1968.", Serialized Form

Attributes:

specializes WAStar with W=1.

Nested Class Summary

Nested classes/interfaces inherited from class orbital.algorithm.template.BestFirstSearch

BestFirstSearch.OptionIterator

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

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic

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

EvaluativeAlgorithm.EvaluationComparator

Constructor Summary

AStar(Function heuristic)
Create a new instance of A^* search.

Method Summary

Function	complexity() O(bd) where b is the branching factor and d the solution depth.
Function	getEvaluation() f(n) = g(n) + h(n).
Function	getHeuristic() Get the heuristic function used.
boolean	isOptimal() Optimal if heuristic is admissible.
void	setHeuristic(Function heuristic) Set the heuristic function to use.
Function	spaceComplexity() O(bd) where b is the branching factor and d the solution depth.

Methods inherited from class orbital.algorithm.template.BestFirstSearch

createTraversal

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

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

solve

Constructor Detail

AStar

public AStar(Function heuristic)

Create a new instance of A^* search. Which is a best first search using the evaluation function f(n) = g(n) + h(n).

Parameters:

heuristic - the heuristic cost function h:S→R embedded in the evaluation function f.

See Also:

getEvaluation()

Method Detail

getHeuristic

public Function getHeuristic()

Description copied from interface: HeuristicAlgorithm

Get the heuristic function used.

Specified by:

getHeuristic in interface HeuristicAlgorithm

Returns:

the heuristic cost function h:S→R estimating h^*.

setHeuristic

public void setHeuristic(Function heuristic)

Description copied from interface: HeuristicAlgorithm

Set the heuristic function to use.

An heuristic cost function h:S→R is estimating the cost to get from a node n to a goal G. For several heuristic algorithms this heuristic function needs to be admissible

h ≤ h^* i.e. h is a lower bound for the effective cost function h^*. Then the pathmax heuristic f(s') := max {f(s), g(s') + h(s')} (for transitions s→s'=t(s,a) with a∈A(s)) is monotonic.

A heuristic cost function h is monotonic :⇔ the f-costs (with h) do not decrease in any path from the initial state ⇔ h obeys the triangular inequality

∀s∈S,a∈A(s) h(s) ≤ h(s') + c(s,a) with s' = t(s,a) i.e. the sum of the costs from A to C and from C to B must not be less than the cost from A to B.

A simple improvement for heuristic functions is using pathmax.

Specified by:

setHeuristic in interface HeuristicAlgorithm

Parameters:

heuristic - the heuristic cost function h:S→R estimating h^*. h will be embedded in the evaluation function f.

See Also:

"Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, Massachusetts. 1984."

getEvaluation

public Function getEvaluation()

f(n) = g(n) + h(n).

Specified by:

getEvaluation in interface EvaluativeAlgorithm

Specified by:

getEvaluation in interface HeuristicAlgorithm

Returns:

the evaluation function f:S→R used to evaluate (either utility or cost) value of states.

complexity

public Function complexity()

O(b^d) where b is the branching factor and d the solution depth.

Specified by:

complexity in interface AlgorithmicTemplate

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.

Specified by:

spaceComplexity in interface AlgorithmicTemplate

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 if heuristic is admissible.

Specified by:

isOptimal in class GeneralSearch

Returns:

whether this search algorithm is optimal, i.e. whether solutions found are guaranteed to be optimal.