Orbital library

## orbital.algorithm.template Interface GreedyProblem

Type Parameters:
`C` - the type of individual candidates.
All Superinterfaces:
AlgorithmicProblem

`public interface GreedyProblemextends AlgorithmicProblem`

Hook class for Greedy Algorithms.

Let U⊆℘(C) be a family of subsets of a finite set C. Further let w:CR be the weighting function (usually w≥0).
filtered system
(C,U) is called a "filtered" system of sets, if
• ∅∈U
• ∀A⊆B∀B∈U A∈U
Note: filtered systems here are just the contrary to filters in the topological sense.
matroid
A filtered system of sets (C,U) is called a matroid, if it satisfies the exchange property
• A,BU (|A|<|B| → ∃x∈BA A∪{x}∈U)
weight of a set
The total weight of the set MU is
w(M) := ∑m∈M w(m)
The optimization problem belonging to a filtered system (C,U) and a weighting function w:CR is to find a maximal (according to ⊆) set M*U with optimal weight
w(M*) = maxMU w(M)

##### Proposition
Let (C,U) be a filtered system of sets. The Greedy-Algorithm finds an optimal solution for each weighting function w:CR, if and only if (C,U) is a matroid.
##### Note
Even if (C,U) is not a matroid, the greedy algorithm may still find optimal solutions for some, but not for all weighting functions w:CR. If in fact, a greedy algorithm does not even yield an optimal solution, it may nevertheless be a good heuristic.

However note that some very simple greedy algorithms may be more intuitive if formulated in a single implementation method rather than encapsulated in an instance of GreedyProblem.

Author:
André Platzer
`Greedy`

Method Summary
` java.util.List` `getInitialCandidates()`
get the initial set of candidates.
` Function` `getWeightingFor(java.util.List choices)`
Get an objective function.
` boolean` `isPartialSolution(java.util.List choices)`
Test whether the given list of choices still is a valid (partial) solution.
` boolean` `isSolution(java.util.List choices)`
Check whether the given list of choices is a valid solution to the problem.
` java.util.List` `nextCandidates(java.util.List candidates)`
Get the next set of candidates.
` java.util.List` ```nextPartialSolution(java.util.List choices, java.lang.Object new_choice)```
Extends the choices with a new_choice if that is feasible, otherwise nothing is changed.

Method Detail

### getInitialCandidates

`java.util.List getInitialCandidates()`
get the initial set of candidates.

Returns:
the initial set of candidates, usually C.
`nextCandidates(List)`
Preconditions:
true
Postconditions:
RES is the initial alternative candidates for the solution.

### nextPartialSolution

```java.util.List nextPartialSolution(java.util.List choices,
java.lang.Object new_choice)```
Extends the choices with a new_choice if that is feasible, otherwise nothing is changed.

Parameters:
`choices` - the valid partial solution M.
`new_choice` - the new choice x with maximum local weight.
Returns:
usually M∪{x}, the choices extended by the new_choice
`isPartialSolution(List)`
Preconditions:
choices is a valid partial solution, new_choice has maximum local weight.
Postconditions:
RES new solution value that includes new_choice if feasible. Usually RES=choices∪{new_choice}.

### isPartialSolution

`boolean isPartialSolution(java.util.List choices)`
Test whether the given list of choices still is a valid (partial) solution.

Parameters:
`choices` - a list M of partial solution values.
Returns:
whether MU, i.e. whether M is independent and thus an admissible partial solution.
`nextPartialSolution(List,Object)`, `isSolution(List)`
Postconditions:
RES indicates whether valid partial solution

### nextCandidates

`java.util.List nextCandidates(java.util.List candidates)`
Get the next set of candidates.

If the list of candidates does not change this method can simply return candidates.

Parameters:
`the` - remaining set of candidates C not yet considered.
Returns:
the next alternative candidates for the solution. For strict matroids simply C.
`getInitialCandidates()`
Preconditions:
candidates are the current alternative candidates for the solution.

### isSolution

`boolean isSolution(java.util.List choices)`
Check whether the given list of choices is a valid solution to the problem.

`isPartialSolution(List)`
Preconditions:
no more alternative candidatess or isPartialSolution is no longer true.
Postconditions:
RES indicates whether we found a solution to the problem

### getWeightingFor

`Function getWeightingFor(java.util.List choices)`
Get an objective function.

This objective function will be maximized which means that objects with a higher objective value are strictly preferred.

If the weighting function never changes for this problem, consider using a singleton instead of creating a new one on each call. This will increase efficiency.

Parameters:
`choices` - the current situation of choices.
Returns:
the objective weighting function w:CR on the candidates.
Preconditions:
choices is a valid partial solution.
Postconditions:
RES the objective weighting function for the current situation of choices which will only be referenced until the next call of this function. Usually w≥0.
Note:
if this problem is a matroid, greedy will find a soltuion for any weighting function w. So we could set the weighting function in Greedy, directly, then.

Orbital library
1.3.0: 11 Apr 2009