orbital.algorithm.template
Class DynamicProgramming

java.lang.Object
  orbital.algorithm.template.DynamicProgramming

All Implemented Interfaces:

AlgorithmicTemplate

public class DynamicProgramming
extends java.lang.Object
implements AlgorithmicTemplate

Framework (template class) for Dynamic Programming Algorithms.

Requires that the problem exhibits optimal substructure, i.e. optimal solutions to subproblems somehow generalize to optimal solutions of the whole problem. Then each optimal solutions carries within it independent optimal solutions to its subproblems. Further requires that the subproblems overlap, i.e. a simple recursive formulation would revisit the same subproblem over and over again.

bottom-up technique:

• A table of all sub-instance results is constructed.
• The entries corresponding to the smallest sub-instances are initiated at the start of the algorithm.
• The remaining entries are filled in following a precise order (that corresponds to increasing sub-instance size) using only those entries that have already been computed.
• Each entry is calculated exactly once.
• The final value computed is the solution to the initial problem instance.
• Implementation is by iteration (never by recursion, even though the analysis of a problem may naturally suggest a recursive solution).

top-down technique:

• Use the natural but inefficient recursive algorithm to solve the problem, and memoize results.

Author:

André Platzer

See Also:

DynamicProgrammingProblem, Greedy, HeuristicAlgorithm.PatternDatabaseHeuristic, "R. E. Bellman. Dynamic Programming. Princeton Universit Press, Princeton, NJ, 1957."

Nested Class Summary

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

AlgorithmicTemplate.Configuration

Constructor Summary

DynamicProgramming()

Method Summary

Function	complexity() O(n2)
static java.lang.Object	getSolutionPart(int[] partSpecification, java.lang.Object[] partialSolutions) Get the element in the (possibly multi-dimensional) array partialSolutions specified by the part specification.
static void	setSolutionPart(int[] partSpecification, java.lang.Object[] partialSolutions, java.lang.Object value)
java.lang.Object	solve(AlgorithmicProblem p) Generic solve method for a given algorithmic problem.
java.lang.Object	solve(DynamicProgrammingProblem p) solves by dynamic programming.
Function	spaceComplexity() Measure for the asymptotic space complexity of the central solution operation in O-notation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DynamicProgramming

public DynamicProgramming()

Method Detail

solve

public java.lang.Object solve(AlgorithmicProblem p)

Description copied from interface: AlgorithmicTemplate

Generic solve method for a given algorithmic problem.

Specified by:

solve in interface AlgorithmicTemplate

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)

solve

public java.lang.Object solve(DynamicProgrammingProblem p)

solves by dynamic programming.

Returns:

the solution object as merged from the partial problems.

Postconditions:

solution is a merge of partial solutions.

complexity

public Function complexity()

O(n²)

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()

Description copied from interface: AlgorithmicTemplate

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

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)

getSolutionPart

public static java.lang.Object getSolutionPart(int[] partSpecification,
                                               java.lang.Object[] partialSolutions)

Get the element in the (possibly multi-dimensional) array partialSolutions specified by the part specification.

Returns:

partialSolutions[partSpecification[0]][partSpecification[1]]...[partSpecification[partSpecification.length-1]] .

See Also:

Utility.getPart(Object[],int[])

Preconditions:

partSpecification.length is not lower than the number of dimensions for partialSolutions.

setSolutionPart

public static void setSolutionPart(int[] partSpecification,
                                   java.lang.Object[] partialSolutions,
                                   java.lang.Object value)