Greedy-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Greedy-Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen, die in der Informatik auftreten. Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht (z. B. Gradientenverfahren). Um unter den Folgezuständen eine Auswahl zu treffen, wird oft eine Bewertungsfunktion verwendet.

Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

Optimierungsprobleme auf Unabhängigkeitssystemen[Bearbeiten]

Ein Greedy-Algorithmus findet für ein Optimierungsproblem auf Unabhängigkeitssystemen genau dann die optimale Lösung für alle Bewertungsfunktionen, wenn die zulässigen Lösungen die unabhängigen Mengen eines Matroids sind. Sonst führt der Algorithmus lediglich zu einem lokalen Optimum. Beispiele dafür sind das Rucksackproblem und das Problem des Handlungsreisenden. Bei diesen Problemen ist es wesentlich aufwändiger, die optimale Lösung zu finden, da die Probleme NP-vollständig sind.

Algorithmus für das Maximierungsproblem[Bearbeiten]

Zu einem Matroid (E,U) sei eine Gewichtsfunktion w:E\rightarrow \mathbb{R}^+ gegeben. Der folgende Algorithmus findet eine schwerste unabhängige Menge, bestimmt also ein F\in U, das w(F) := \sum_{e\in F} w(e) maximiert:

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

Verallgemeinerbarkeit[Bearbeiten]

Der Algorithmus löst auch Maximierungs- und Minimierungsprobleme zu beliebigen Gewichtsfunktionen w: E\to \mathbb{R}: In einer Lösung für das Maximierungsproblem treten negative Gewichte nicht auf, Elemente mit negativem Gewicht können also vom Algorithmus ignoriert werden. Die Lösung des Problems, eine minimale unabhängige Menge zu finden, können wir auf die Lösung des Maximierungsproblems zurückführen, indem wir die Gewichte durch ihre additiven Inversen ersetzen.

Laufzeit[Bearbeiten]

Ist L die Laufzeit der Prüfung einer Menge auf Unabhängigkeit, so ist die Laufzeit des Algorithmus durch \mathcal{O}(|E|\cdot(\log(|E|+L))) gegeben. Im besten Fall wird sie also durch das Sortierverfahren dominiert. Wenn die Unabhängigkeitsprüfung dagegen NP-vollständig ist, ist der Algorithmus praktisch nutzlos.

Algorithmus für das Minimierungsproblem[Bearbeiten]

Zu einem Matroid (E,U) sei eine Gewichtsfunktion w:E\rightarrow \mathbb{R}^+ gegeben. Der folgende Algorithmus findet eine leichteste Basis, bestimmt also unter den kardinalitätsmaximalen B\in U eines, das c(B) := \sum_{e\in B} c(e) minimiert:

  • Sortiere E, so dass E=\{e_1, \ldots, e_n\} mit w(e_1) \geq w(e_2) \geq \cdots \geq w(e_n)
  • T := E
  • Für jedes i von 1 bis n:
Enthält T\setminus e_i eine Basis, so setze T := T \setminus e_i.
  • Gib T aus.

Vergleich zum Maximierungsproblem, Verallgemeinerbarkeit[Bearbeiten]

Da wir positive Gewichte vergeben, ist das Problem, nach einer leichtesten Basis-Obermenge zu suchen, äquivalent. Dieses Problem ist dual zum Maximierungsproblem und kann analog auf beliebige Gewichtsfunktionen und das entsprechende Minimierungsproblem verallgemeinert werden.

Laufzeit[Bearbeiten]

Ist L die Laufzeit der Prüfung, ob eine Teilmenge von E Obermenge einer Basis ist, so ist die Laufzeit des Algorithmus durch \mathcal{O}(|E|\cdot(\log(|E|+L))) gegeben. Im besten Fall wird sie also durch das Sortierverfahren dominiert. Wenn die Basis-Obermengen-Prüfung dagegen NP-vollständig ist, ist der Algorithmus praktisch nutzlos.

Beispiele[Bearbeiten]

Literatur[Bearbeiten]