Orbital library

orbital.algorithm.template
Class Greedy

java.lang.Object
  extended by orbital.algorithm.template.Greedy
All Implemented Interfaces:
AlgorithmicTemplate

public class Greedy
extends java.lang.Object
implements AlgorithmicTemplate

Framework (template class) for Greedy Algorithms. The greedy algorithm does only perform local decisions.

Author:
André Platzer
See Also:
GreedyProblem, DynamicProgramming, HillClimbing
Attributes:
stateless
Note:
an optimization could keep the candidates in a heap if only our GreedyProblem would promise not to remove any candidates (and tells us new candidates only instead of those that we already knew). However which heap to choose might depend on the problem, binomial, fibonacci, ...

Nested Class Summary
 
Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate
AlgorithmicTemplate.Configuration
 
Constructor Summary
Greedy()
           
 
Method Summary
 Function complexity()
          O(n*log n + n*f(n)) for n=|C| candidates.
 java.lang.Object solve(AlgorithmicProblem gp)
          solves by greedy.
 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

Greedy

public Greedy()
Method Detail

solve

public java.lang.Object solve(AlgorithmicProblem gp)
solves by greedy.

The canonical greedy algorithm for a filtered system of sets (C,U) is

 {e1,…,en} := C sorted such that w(e1)≥…≥w(en)
 S :=for i = 1 to n do
     if S{ei}∈U then
         // optionally check that w(ei)≥0 if w has negative values
         S := S  {ei}
     end if
 end for
 return S
 
Observe that the greedy algorithm does only perform local decisions.

Somewhat generalized, with a little more explicit structure, and adapted to the concrete methods in the hook class, the greedy algorithm in SETL looks like this:

 Set greedy(Set C) {
     Set S := ∅;
     while S is partialSolution and C ≠ ∅ do
         // weight is quality criterium
         retract x from C such that w(x) is maximal (with regard to S);
         // nextPartialSolution computes new partial solution
         S := nextPartialSolution(S,x);
         // generalized case with changing candidates
         C := nextCandidates(C);
     end while;
     if S is solution then
         return S;
     else
         return ∅;
 }
 

Specified by:
solve in interface AlgorithmicTemplate
Parameters:
gp - algorithmic problem hook class which must fit the concrete algorithmic template framework implementation.
Returns:
the list of the candidates chosen for the solution.
See Also:
Function.apply(Object)

complexity

public Function complexity()
O(n*log n + n*f(n)) for n=|C| candidates. Provided that the running time of the independency check in GreedyProblem.isPartialSolution(List) is f(n).

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.