Orbital library

Interface HeuristicAlgorithm

All Superinterfaces:
AlgorithmicTemplate, EvaluativeAlgorithm
All Known Implementing Classes:
AStar, BranchAndBound, GaussSeidelDynamicProgramming, HillClimbing, IterativeDeepeningAStar, IterativeExpansion, MarkovDecisionProcess.DynamicProgramming, ParallelBranchAndBound, RealTimeDynamicProgramming, SimulatedAnnealing, ThresholdAccepting, WAStar

public interface HeuristicAlgorithm
extends EvaluativeAlgorithm

Interface for heuristic (search) algorithms.

Also called informed search algorithms or informed planning algorithms.

André Platzer

Nested Class Summary
static class HeuristicAlgorithm.Configuration
          Algorithmic configuration objects for heuristic algorithms.
static class HeuristicAlgorithm.PatternDatabaseHeuristic
          An heuristic function that uses a pattern database.
Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm
Method Summary
 Function getEvaluation()
          Get the evaluation function used while processing..
 Function getHeuristic()
          Get the heuristic function used.
 void setHeuristic(Function heuristic)
          Set the heuristic function to use.
Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate
complexity, solve, spaceComplexity

Method Detail


Function getHeuristic()
Get the heuristic function used.

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


void setHeuristic(Function heuristic)
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.

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."
heuristic is functional, i.e. x.equals(y) ⇒ heuristic.apply(x).equals(heuristic.apply(y))


Function getEvaluation()
Get the evaluation function used while processing.

Also called objective function.


The evaluation function f may depend upon an heuristic cost function h:S→R

Specified by:
getEvaluation in interface EvaluativeAlgorithm
the evaluation function f:S→R used to evaluate (either utility or cost) value of states.

Orbital library
1.3.0: 11 Apr 2009

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