Orbital library

Package orbital.algorithm.template

A framework for general algorithmic evaluation schemes including search and planning algorithms.


Interface Summary
AlgorithmicConfiguration Algorithmic configurations provide the glue between a problem and an algorithm used for solving it.
AlgorithmicProblem AlgorithmicProblem interface used for tagging hook class interfaces for algorithmic templates.
AlgorithmicTemplate Base interface for algorithmic template frameworks.
BacktrackingProblem Hook class for Backtracking Algorithms
DivideAndConquerProblem Hook class for problems solved by DivideAndConquer.
DynamicProgrammingProblem Hook class for problems solved by DynamicProgramming.
EvaluativeAlgorithm Interface for evaluative algorithms.
GeneralSearchProblem Hook class for GeneralSearch algorithm.
GreedyProblem Hook class for Greedy Algorithms.
HeuristicAlgorithm Interface for heuristic (search) algorithms.
MarkovDecisionProblem Hook class for MarkovDecisionProcess algorithm.
MarkovDecisionProblem.Transition Represents a transition option during a Markov decision process.
ProbabilisticAlgorithm Tags probabilistic algorithms leading to approximative solutions.
TransitionModel Represents a transition model.
TransitionModel.Transition Represents (information about) a transition option during a transition model.

Class Summary
AlgorithmicTemplate.Configuration Default implementation of algorithmic configuration objects.
AStar A* search class.
Backtracking Framework (template class) for Backtracking Algorithms.
BestFirstSearch BestFirstSearch class (BFS).
BestFirstSearch.OptionIterator An iterator over a state space in best-first order.
BranchAndBound Branch-and-bound (B&B).
BreadthFirstSearch BreadthFirstSearch class (BrFS).
BreadthFirstSearch.OptionIterator An iterator over a state space in breadth-first order.
DelegateGeneralSearchProblem Delegates to a GeneralSearchProblem.
DepthFirstSearch DepthFirstSearch class (DFS).
DepthFirstSearch.OptionIterator An iterator over a state space in depth-first order.
DivideAndConquer Framework (template class) for Divide and Conquer Algorithms.
DynamicProgramming Framework (template class) for Dynamic Programming Algorithms.
DynamicProgrammingOptimizingProblem Base hook class for problems solved by DynamicProgramming for optimization.
EvaluativeAlgorithm.EvaluationComparator The canonical comparator induced by the evaluation function f(n).
GaussSeidelDynamicProgramming Gauß-Seidel dynamic programming.
GeneralBoundingSearch Abstract general bounding search scheme.
GeneralSearch Abstract general search algorithm scheme.
GeneralSearch.OptionIterator Abstract implementation base class for iterators determining the traversal order.
GeneralSearchProblem.Transition Represents an option node during a search problem.
Greedy Framework (template class) for Greedy Algorithms.
HeuristicAlgorithm.Configuration Algorithmic configuration objects for heuristic algorithms.
HeuristicAlgorithm.PatternDatabaseHeuristic An heuristic function that uses a pattern database.
HillClimbing Hill-climbing search.
IterativeBroadening Iterative Broadening (IB).
IterativeDeepening Iterative Deepening (ID).
IterativeDeepeningAStar Iterative Deepening A* (IDA*).
IterativeExpansion Iterative Expansion (IE).
LocalOptimizerSearch General search scheme for local optimizing search.
LocalOptimizerSearch.LocalSelection The local selection mechanism used to evaluate states.
LocalOptimizerSearch.OptionIterator An iterator over a state space in "choosy" random order.
MarkovDecisionProblem.DefaultTransition Default implementation of transition options for Markov decision processes.
MarkovDecisionProcess Markov decision process (MDP).
MarkovDecisionProcess.DynamicProgramming Abstract base class for Markov decision processes solved per dynamic programming.
OpenClosedGeneralSearchProblem GeneralSearchProblem wrapper keeping track of open and closed sets.
ParallelBranchAndBound Parallel branch-and-bound algorithm.
RealTimeDynamicProgramming Real-Time Dynamic Programming (RTDP).
SimulatedAnnealing Simulated Annealing (SA) search.
ThresholdAccepting Threshold Accepting (TA) search.
TransitionPath A (randomized) path through state space S by transition τ of a TransitionModel.
WAStar WA* search class.

Exception Summary
InapplicableActionException Thrown to indicate that an action was not applicable in the state.

Package orbital.algorithm.template Description

A framework for general algorithmic evaluation schemes including search and planning algorithms. This package contains algorithmic template classes (or algorithmic patterns) for rapid-prototyping and sophisticated search strategies and planning in state spaces.

Algorithmic templates get called along with a problem-specific implementation of the corresponding hook class to solve the problem. The hook class interface can be implemented in order to apply one of the prefabricated algorithms. Apart from the relief from implementing the algorithm itself, using algorithmic templates often has the powerful advantage that several different implementations can be interchanged freely without the need to change more than just a single constructor call to the concrete algorithm. Once a problem has been modeled accordingly by implementing its hook class, concrete solution algorithms can even be interchanged at runtime.

This freedom of choice concerning the concrete algorithm enables clients to find the optimal solution algorithm for the actual problem experimentally. Very sophisticated problems may even be tackled by switching algorithms, depending on the dynamic behaviour and progress of the solution process. Because of the common interface to all algorithms solving a specific problem class, switching algorithms is simple. You may also profit massively from nested search or nested optimization where one algorithm works on the solutions of another algorithm.

Important classes are:

See Also:
Strategy Pattern, Table of Algorithms in Comparison.

Orbital library
1.3.0: 11 Apr 2009

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