Orbital library

orbital.algorithm.template
Class Backtracking

java.lang.Object
  extended by 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(nn) 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)

Orbital library
1.3.0: 11 Apr 2009

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