
Orbital library  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object orbital.algorithm.template.Greedy
public class Greedy
Framework (template class) for Greedy Algorithms. The greedy algorithm does only perform local decisions.
GreedyProblem
,
DynamicProgramming
,
HillClimbing
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 Onotation. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Constructor Detail 

public Greedy()
Method Detail 

public java.lang.Object solve(AlgorithmicProblem gp)
The canonical greedy algorithm for a filtered system of sets (C,U) is
{e_{1},…,e_{n}} := C sorted such that w(e_{1})≥…≥w(e_{n}) S := ∅ for i = 1 to n do if S∪{e_{i}}∈U then // optionally check that w(e_{i})≥0 if w has negative values S := S ∪ {e_{i}} end if end for return SObserve 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 ∅; }
solve
in interface AlgorithmicTemplate
gp
 algorithmic problem hook class which must fit the concrete
algorithmic template framework implementation.
Function.apply(Object)
public Function complexity()
GreedyProblem.isPartialSolution(List)
is f(n).
complexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
public Function spaceComplexity()
AlgorithmicTemplate
spaceComplexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)

Orbital library 1.3.0: 11 Apr 2009 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 