Orbital library

orbital.algorithm.template
Interface DivideAndConquerProblem

All Superinterfaces:
AlgorithmicProblem

public interface DivideAndConquerProblem
extends AlgorithmicProblem

Hook class for problems solved by DivideAndConquer.

Author:
Uwe Aßmann, André Platzer
See Also:
DivideAndConquer

Method Summary
 java.lang.Object basicSolve()
          Solve the base case.
 DivideAndConquerProblem[] divide()
          Divide this problem into several problem parts which can be solved independently.
 java.lang.Object merge(java.lang.Object[] partialSolutions)
          Merge several partial solutions to a complete solution.
 boolean smallEnough()
          Whether this problem is small enough to be solved as the base case using basicSolve().
 

Method Detail

smallEnough

boolean smallEnough()
Whether this problem is small enough to be solved as the base case using basicSolve().

See Also:
basicSolve()

basicSolve

java.lang.Object basicSolve()
Solve the base case.

Returns:
the solution for this base case.
See Also:
smallEnough()
Preconditions:
smallEnough()

divide

DivideAndConquerProblem[] divide()
Divide this problem into several problem parts which can be solved independently. Solving will then continue with these parts in ascending order, before they will be merged.

Returns:
an array of (smaller) sub problems.
Preconditions:
¬smallEnough()

merge

java.lang.Object merge(java.lang.Object[] partialSolutions)
Merge several partial solutions to a complete solution.

For single-sided divide and conquer, simply returns this as the answer.

Parameters:
partialSolutions - partial solutions
Returns:
the complete solution consisting of the partial solutions.
Preconditions:
¬smallEnough()

Orbital library
1.3.0: 11 Apr 2009

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