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