orbital.algorithm.template
Interface GreedyProblem
 Type Parameters:
C
 the type of individual candidates.
 All Superinterfaces:
 AlgorithmicProblem
public interface GreedyProblem
 extends AlgorithmicProblem
Hook class for Greedy Algorithms.
Let U⊆℘(C) be a family of subsets of a finite set C.
Further let w:C→R be the weighting function (usually w≥0).
 filtered system

(C,U) is called a "filtered" system of sets, if
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,B∈U (A<B → ∃x∈B∖A A∪{x}∈U)
 weight of a set

The total weight of the set M∈U is
w(M) := ∑_{m∈M} w(m)
The optimization problem belonging to a filtered system (C,U) and
a weighting function w:C→R
is to find a maximal (according to ⊆) set M^{*}∈U
with optimal weight
w(M^{*}) = max_{M∈U} w(M)
Proposition
Let (C,U) be a filtered system of sets.
The GreedyAlgorithm finds an optimal solution for
each weighting function w:C→R,
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:C→R.
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
 See Also:
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. 
getInitialCandidates
java.util.List getInitialCandidates()
 get the initial set of candidates.
 Returns:
 the initial set of candidates, usually C.
 See Also:
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
 See Also:
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 M∈U, i.e.
whether M is independent and thus an admissible partial solution.
 See Also:
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.
 See Also:
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.
 See Also:
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:C→R 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.
Copyright © 19962009 André Platzer
All Rights Reserved.