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 subset of 2^(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

• Ø in U
• for all A subset of B for all B in U A in 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

• for all A,B in U (|A|<|B| -> exist x in B\A A union {x} in U)

weight of a set

The total weight of the set M in U is w(M) := Σ_{m in 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 subset of ) set M^* in U with optimal weight w(M^*) = max_{M in U} w(M)

Proposition

Let (C,U) be a filtered system of sets. The Greedy-Algorithm 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.

Method Detail

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 union {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 union {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 in 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.