Greedy-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Greedy-Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen in der Informatik. 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 (berechnet durch eine Bewertungsfunktion) verspricht (z. B. Gradientenverfahren).

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

Anschauliches Beispiel

[Bearbeiten | Quelltext bearbeiten]

Ein Wanderer möchte möglichst hoch hinaus. Es ist jedoch so neblig, dass er nur 5 Meter weit sehen kann. Er verfolgt eine einfache Strategie: Er sieht sich in seiner Umgebung um, welcher Punkt der höchste ist und geht dann dorthin. Dort schaut er sich wieder um, welcher Punkt der höchste ist, geht dorthin, und so weiter, bis er keinen höheren Punkt mehr findet.

Dieses Beispiel zeigt die typischen Eigenschaften eines Greedy-Algorithmus:

  • Um das große Ziel zu erreichen, sind kleine Einzelschritte nötig. Der Wanderer geht in jedem Schritt maximal 5 Meter weit.
  • In jedem der Einzelschritte sind nur begrenzt Informationen verfügbar. Der Wanderer sieht jeweils nur die umliegenden 5 Meter.
  • Nachdem ein Einzelschritt ausgeführt wurde, wird dieser Schritt nicht mehr zurückgenommen. Der Wanderer denkt nicht darüber nach, 3 Schritte zurückzugehen, um an einem anderen Ort einen besseren Weg zu finden.
  • Die gefundene Lösung ist nicht notwendigerweise die global optimale. Der Wanderer erreicht wahrscheinlich den Gipfel eines kleinen Hügels statt den eines großen Berges.
  • Je nach Ausgangssituation kann sich die gefundene Lösung stark unterscheiden.

Optimierungsprobleme auf Unabhängigkeitssystemen

[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Zu einem Matroid sei eine Gewichtsfunktion gegeben. Der folgende Algorithmus findet eine schwerste unabhängige Menge, bestimmt also ein , das maximiert:

  1  // Ordne alle Elemente in  nach absteigendem Gewicht
  2  
  3  
  4  ;
  5  
  6  for (k = 1; k <= n; k++) {
  7    if 
  8      
  9  }
 10  
 11  Ausgabe der Lösung 

Verallgemeinerbarkeit

[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus löst auch Maximierungs- und Minimierungsprobleme zu beliebigen Gewichtsfunktionen : 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, kann auf die Lösung des Maximierungsproblems zurückgeführt werden, indem man die Gewichte durch ihre additiven Inversen ersetzt.

Ist L die Laufzeit der Prüfung einer Menge auf Unabhängigkeit, so ist die Laufzeit des Algorithmus durch 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 | Quelltext bearbeiten]

Zu einem Matroid sei eine Gewichtsfunktion gegeben. Der folgende Algorithmus findet eine leichteste Basis, bestimmt also unter den kardinalitätsmaximalen eines, das minimiert:

  • Sortiere , so dass mit
  • Für jedes von 1 bis :
Enthält eine Basis, so setze .
  • Gib aus.

Vergleich zum Maximierungsproblem, Verallgemeinerbarkeit

[Bearbeiten | Quelltext bearbeiten]

Da positive Gewichte vergeben sind, 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.

Ist die Laufzeit der Prüfung, ob eine Teilmenge von Obermenge einer Basis ist, so ist die Laufzeit des Algorithmus durch 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.