Greedy-Algorithmus - LinkFang.de





Greedy-Algorithmus


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 (berechnet durch eine Bewertungsfunktion) verspricht (z. B. Gradientenverfahren).

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

Optimierungsprobleme auf Unabhängigkeitssystemen

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

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

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

Verallgemeinerbarkeit

Der Algorithmus löst auch Maximierungs- und Minimierungsprobleme zu beliebigen Gewichtsfunktionen [math]w: E\to \mathbb{R}[/math]: 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.

Laufzeit

Ist L die Laufzeit der Prüfung einer Menge auf Unabhängigkeit, so ist die Laufzeit des Algorithmus durch [math]\mathcal{O}(|E|\cdot(\log(|E|+L)))[/math] 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

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

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

Vergleich zum Maximierungsproblem, Verallgemeinerbarkeit

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.

Laufzeit

Ist L die Laufzeit der Prüfung, ob eine Teilmenge von E Obermenge einer Basis ist, so ist die Laufzeit des Algorithmus durch [math]\mathcal{O}(|E|\cdot(\log(|E|+L)))[/math] 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

Literatur


Kategorien: Optimierungsalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Greedy-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.