orbital.algorithm.template
Class Backtracking

java.lang.Object
  orbital.algorithm.template.Backtracking

All Implemented Interfaces:

AlgorithmicTemplate

public class Backtracking
extends java.lang.Object
implements AlgorithmicTemplate

Framework (template class) for Backtracking Algorithms.

Note that Backtracking is also a common mechanism for resolving nondeterministic choices.

Author:

Uwe Aßmann, André Platzer

See Also:

BacktrackingProblem, DepthFirstSearch

Nested Class Summary

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

AlgorithmicTemplate.Configuration

Constructor Summary

Backtracking()

Method Summary

Function	complexity() O(nn) in the worst case.
java.lang.Object	solve(AlgorithmicProblem p) Generic solve method for a given algorithmic problem.
java.util.List	solve(BacktrackingProblem problem_solving) solves by backtracking.
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

Backtracking

public Backtracking()

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.util.List solve(BacktrackingProblem problem_solving)

solves by backtracking.

Returns:

an array of the solution choices.

complexity

public Function complexity()

O(nⁿ) in the worst case.

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)