orbital.algorithm.template
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.

Author:

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

EvaluativeAlgorithm.EvaluationComparator

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

getHeuristic

Function getHeuristic()

Get the heuristic function used.

Returns:

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

setHeuristic

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.

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."

Preconditions:

heuristic is functional, i.e. x.equals(y) ⇒ heuristic.apply(x).equals(heuristic.apply(y))

getEvaluation

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

Returns:

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