Greedy algorithm

Greedy algorithms or greedy algorithms form a special class of algorithms in computer science . They are characterized by the fact that they gradually select the subsequent state that promises the greatest profit or the best result (calculated by an evaluation function ) at the time of the selection (e.g. gradient method ).

Greedy algorithms are often fast, but do not solve many problems optimally.

Optimization problems on independence systems

A greedy algorithm finds the optimal solution for all evaluation functions for an optimization problem on independence systems if and only if the feasible solutions are the independent sets of a matroid . Otherwise the algorithm only leads to a local optimum . Examples are the knapsack problem and the Traveling Salesman Problem . With these problems it is much more time-consuming to find the optimal solution, since the problems are NP-complete .

Algorithm for the maximization problem

A weight function is given for a matroid . The following algorithm finds a heaviest independent set, that is, determines one that maximizes: ${\displaystyle (E,U)}$ ${\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}$ ${\displaystyle F\in U}$ ${\displaystyle w(F):=\sum _{e\in F}w(e)}$

  1  // Ordne alle Elemente in  ${\displaystyle E}$ nach absteigendem Gewicht
  2   ${\displaystyle w(e_{1})\geq \ldots \geq w(e_{n})}$
  3  
  4   ${\displaystyle T=\emptyset }$;
  5  
  6  for (k = 1; k <= n; k++) {
  7    if  ${\displaystyle (T\cup \{e_{k}\}\in U)}$
  8       ${\displaystyle T=T\cup \{e_{k}\}}$
  9  }
 10  
 11  Ausgabe der Lösung  ${\displaystyle T}$

Generalizability

The algorithm also solves maximization and minimization problems for arbitrary weight functions : In a solution to the maximization problem, negative weights do not occur, elements with negative weights can therefore be ignored by the algorithm. The solution to the problem of finding a minimal independent set can be reduced to solving the maximization problem by replacing the weights with their additive inverses. ${\displaystyle w\colon E\to \mathbb {R} }$

running time

If L is the running time of checking a set for independence, the running time of the algorithm is given by. In the best case, it is dominated by the sorting process . On the other hand, if the independence check is NP-complete , the algorithm is practically useless. ${\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}$

Algorithm for the minimization problem

A weight function is given for a matroid . The following algorithm finds the easiest basis, i.e. determines one of the cardinality maximums that minimizes: ${\displaystyle (E,U)}$ ${\displaystyle w\colon E\rightarrow \mathbb {R} ^{+}}$ ${\displaystyle B\in U}$ ${\displaystyle c(B):=\sum _{e\in B}c(e)}$

• Sort so that with ${\displaystyle E}$ ${\displaystyle E=\{e_{1},\ldots ,e_{n}\}}$ ${\displaystyle w(e_{1})\geq w(e_{2})\geq \cdots \geq w(e_{n})}$
• ${\displaystyle T:=E}$
• For each from 1 to : ${\displaystyle i}$ ${\displaystyle n}$

Contains a base, so sit . ${\displaystyle T\setminus e_{i}}$ ${\displaystyle T:=T\setminus e_{i}}$

• Spend . ${\displaystyle T}$

Comparison to the maximization problem, generalizability

Since positive weights are given, the problem of looking for a lightest base superset is equivalent. This problem is dual to the maximization problem and can be generalized analogously to any weight functions and the corresponding minimization problem.

running time

If the runtime of the check is whether a subset of a superset is a basis, the runtime of the algorithm is given by. In the best case, it is dominated by the sorting process . On the other hand, if the base superset check is NP-complete , the algorithm is practically useless. ${\displaystyle L}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {O}}(|E|\cdot (\log(|E|+L)))}$

Examples

• Kruskal's algorithm for finding a minimal spanning tree
• Prim's algorithm for the search for a minimal spanning tree (but the underlying set system - the set of trees - is not an independence system)
• Dijkstra's algorithm for finding a shortest path
• Algorithm Successive inclusion to solve combinatorial optimization problems

literature

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest , Clifford Stein: Introduction to Algorithms. 2nd Edition. MIT Press, 2001, ISBN 0-262-53196-8 .
• Bernhard Korte , Jens Vygen : Combinatorial Optimization. 3. Edition. Springer, 2005, ISBN 3-540-25684-9 .
• James Oxley: Matroid Theory . Oxford Mathematics 1992. ISBN 0-19-853563-5 .
• Christos H. Papadimitriou and Kenneth Steiglitz: Combinatorial Optimization . Algorithms and Complexity. Prentice Hall Inc. 1982. ISBN 0-13-152462-3 .
• Jon Lee: A First Course in Combinatorial Optimization . Cambridge Texts in Applied Mathematics 2004. ISBN 0521010128 .
• Sven Oliver Krumke and Hartmut Noltemeier: Graph theoretical concepts and algorithms . 2nd edition Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1 .