Orbital library

orbital.algorithm.template
Class DynamicProgramming

java.lang.Object
  extended by 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:

top-down technique:

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

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)

Orbital library
1.3.0: 11 Apr 2009

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