orbital.algorithm.template
Interface DynamicProgrammingProblem

All Superinterfaces:

AlgorithmicProblem

All Known Implementing Classes:

DynamicProgrammingOptimizingProblem

public interface DynamicProgrammingProblem
extends AlgorithmicProblem

Hook class for problems solved by DynamicProgramming.

Author:

André Platzer

See Also:

DynamicProgramming

Method Summary

java.lang.Object[]	getInitialPartialSolutions() Get the initial array of partial solutions.
boolean	isSolution(java.lang.Object[] partialSolutions) Check whether the given partial solutions are a valid solution to the problem.
java.lang.Object	merge(java.lang.Object[] partialSolutions) Merge several partial solutions to a complete solution.
int[]	nextPart() Divide this problem into several (dependant) problem parts and return the index description for the next part to solve.
java.lang.Object	solve(int[] part, java.lang.Object[] partialSolutions) Solve the problem part using the partial solutions we already now.

Method Detail

getInitialPartialSolutions

java.lang.Object[] getInitialPartialSolutions()

Get the initial array of partial solutions.

Returns:

(possibly a multi-dimensional) array of objects initialized ready to begin solving.

isSolution

boolean isSolution(java.lang.Object[] partialSolutions)

Check whether the given partial solutions are a valid solution to the problem.

Preconditions:

partialSolutions resulted in repeated calls of solve after a single call to getInitialPartialSolutions.

Postconditions:

RES indicates whether we found a solution to the problem

nextPart

int[] nextPart()

Divide this problem into several (dependant) problem parts and return the index description for the next part to solve. Solving will then continue with this part.

Returns:

an array specifying the indices in the partialSolutions to solve next.

Postconditions:

RES.length is not lower than the number of dimensions for partialSolutions && partialSolutions[RES[0]][RES[1]]...[RES[RES.length-1]] does not raise an exception.

solve

java.lang.Object solve(int[] part,
                       java.lang.Object[] partialSolutions)

Solve the problem part using the partial solutions we already now.

Returns:

the solution for this case.

See Also:

nextPart()

Preconditions:

nextPart() returned part && partialSolutions is constructed by getInitialPartialSolution and solve

merge

java.lang.Object merge(java.lang.Object[] partialSolutions)

Merge several partial solutions to a complete solution.

Parameters:

partialSolutions - partial solutions

Returns:

the complete solution consisting of the partial solutions.