Orbital library

## orbital.algorithm.template Class Greedy

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

`public class Greedyextends java.lang.Objectimplements AlgorithmicTemplate`

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

Author:
André Platzer
`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.
`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).
`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).
`AlgorithmicTemplate.solve(AlgorithmicProblem)`