orbital.algorithm.template
Class Greedy

java.lang.Object
  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)