orbital.algorithm.template
Interface AlgorithmicTemplate

All Known Subinterfaces:

EvaluativeAlgorithm, HeuristicAlgorithm

All Known Implementing Classes:

AStar, Backtracking, BestFirstSearch, BranchAndBound, BreadthFirstSearch, ConcurrenceGeneticAlgorithm, DepthFirstSearch, DivideAndConquer, DynamicProgramming, GaussSeidelDynamicProgramming, GeneralBoundingSearch, GeneralSearch, GeneticAlgorithm, Greedy, HillClimbing, IncrementalGeneticAlgorithm, IterativeBroadening, IterativeDeepening, IterativeDeepeningAStar, IterativeExpansion, LocalOptimizerSearch, MarkovDecisionProcess, MarkovDecisionProcess.DynamicProgramming, ParallelBranchAndBound, RealTimeDynamicProgramming, SimpleGeneticAlgorithm, SimulatedAnnealing, SteadyStateGeneticAlgorithm, ThresholdAccepting, WAStar

public interface AlgorithmicTemplate

Base interface for algorithmic template frameworks.

An algorithmic template is a class that implements a problem-solving algorithm in a general way, such that it is applicable in a multitude of different problems with the same essential structure. It solves this whole bunch of problems by providing a maximum of methods with shared behaviour, and deferring the problem-specific part into a problem interface. Each algorithmic template class has an associated hook interface which is a sub-interface of AlgorithmicProblem and declares the wholes to fill. So this hook interface will contain the part that distinguishes two individual problems of the same common structure solved by the algorithmic template class. In short, algorithmic templates decouple algorithms from the problems such that they the solution procedure is independent of the specific problem at hand. They determine how instances of the problem are solved in general, perhaps still providing some additional parameters for adjusting the concrete problem solving approach.

Of course, algorithmic templates are more useful if they only require a very small and almost declarative algorithmic problem hook.

Author:

André Platzer

See Also:

AlgorithmicProblem, ≈Strategy

Structure:

aggregates problem:AlgorithmicProblem

Nested Class Summary

static class

AlgorithmicTemplate.Configuration Default implementation of algorithmic configuration objects.

Method Summary

Function	complexity() Measure for the asymptotic time complexity of the central solution operation in O-notation.
java.lang.Object	solve(AlgorithmicProblem p) Generic solve method for a given algorithmic problem.
Function	spaceComplexity() Measure for the asymptotic space complexity of the central solution operation in O-notation.

Method Detail

solve

java.lang.Object solve(AlgorithmicProblem p)

Generic solve method for a given algorithmic problem.

Parameters:

p - algorithmic problem hook class which must fit the concrete algorithmic template framework implementation.

Returns:

the solution to the problem p, or null if solving failed.

See Also:

Function.apply(Object)

complexity

Function complexity()

Measure for the asymptotic time complexity of the central solution operation in O-notation.

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:

solve(AlgorithmicProblem)

Preconditions:

true

Postconditions:

RES == OLD(RES) && OLD(this) == this

spaceComplexity

Function spaceComplexity()

Measure for the asymptotic space complexity of the central solution operation in O-notation.

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:

solve(AlgorithmicProblem)

Preconditions:

true

Postconditions:

RES == OLD(RES) && OLD(this) == this