Grundlagen Statistik & Algorithmen, Teil 9 Der Greedy-Algorithmus

Greedy-Algorithmen, oder gierige Algorithmen, bilden eine spezielle Klasse von Optimierungsalgorithmen, 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, so etwa die Berechnung von Wechselgeld oder des kürzesten Wegs. Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

Anbieter zum Thema

Fujitsu Technology Solutions GmbH

Fivetran Germany GmbH

Xpand Solutions GmbH

Ein gieriger Algorithmus möchte in jedem Teilschritt so viel wie möglich im Hinblick auf die Vorgabe erreichen, beispielsweise ein Maximum oder ein Minimum. Eine Anwendung eines solchen Greedy-Algorithmus im täglichen Leben ist die beispielsweise die Herausgabe von Wechselgeld.

Die Vorgabe lautet: Nimm jeweils immer die größte Münze unter dem Zielwert und ziehe sie von diesem ab. Verfahre derart bis Zielwert gleich null. Will man beispielsweise 79 Cent zurückgeben, fängt der Algorithmus sofort mit dem höchsten Münzwert an und macht weiter, bis er den niedrigsten Münzwert erreicht hat, falls das nötig ist: 79 = 50 + 20 + 5 + 2 +2.

In diesem Anwendungsfall klappt das ausgezeichnet. Greedy-Algorithmen berechnen jeweils ein „lokales Optimum“ in jedem Schritt und können daher eventuell ein „globales Optimum“ verpassen. Der Anwender muss also über den Tellerrand hinausschauen, so wie im folgenden Beispiel: Der Zielwert sei 15. Es stehen Münzen mit den Werten 1, 5 und 11 (!) zur Verfügung.

Das „globale Optimum“ lautet: 15 = 5 + 5 + 5. Mit dem Greedy-Algorithmus wird das Optimum verfehlt: 15 = 11 + 1+ 1 + 1 + 1. Erzielt wird zwar der gleiche Wert, aber mit zwei Teilschritten mehr.

Man sieht also, dass der gierige Algorithmus nicht immer das globale Optimum erzielt, aber eine „gierige Heuristik“ dennoch lokal optimale Lösungen liefern kann, die sich einer global optimalen Lösung innerhalb einer vertretbaren Frist annähern. Das rückt die Greedy-Algorithmen, die inzwischen entwickelt worden sind, in die Nähe des Approximationsalgorithmus.

Grundlagen Statistik & Algorithmen, Teil 8

Der Approximationsalgorithmus

Fünf Komponenten

Im Allgemeinen weisen Greedy-Algorithmen fünf Komponenten auf:

• 1. Eine Kandidatenmenge, aus der eine Lösung erzeugt wird;

• 2. eine Auswahlfunktion, die den besten Kandidaten wählt, der der Lösung hinzugefügt werden soll;

• 3. eine Tauglichkeitsfunktion, die verwendet wird, um zu bestimmen, ob ein Kandidat dazu taugt, zu einer Lösung beizutragen;

• 4. eine objektive Funktion, die einer Lösung oder Teillösung einen Wert zuweist, und

• 5. eine Lösungsfunktion, die anzeigt, dass der Nutzer eine vollständige Lösung entdeckt hat.

Greedy-Algorithmen haben eine lange Geschichte in der kombinatorischen Optimierung und der theoretischen Informatik. Greedy-Heuristik liefern allerdings suboptimale Ergebnisse für viele Probleme, sodass sich der Nutzer folgende Fragen stellen sollte:

• Für welche Probleme liefern Greedy-Algorithmen optimale Leistung?

• Für welche Probleme garantieren Greedy-Algorithmen eine annähernd optimale Lösung?

• Für welche Probleme liefert der jeweilige Greedy-Algorithmus garantiert KEINE optimale Lösung?

Der Greedy-Algorithmus und der Handlungsreisende

Die „gierige Strategie“ für das wohlbekannte „Problem des Handlungsreisenden“ ist die folgende Heuristik: „Besuche auf jedem Teilabschnitt der Handlungsreise die nächstgelegene, bislang unbesuchte Stadt.“ Diese Heuristik sucht keine beste Lösung, sondern in einer vernünftigen Anzahl von Rechenschritten. Eine optimale Lösung für ein so komplexes Problem wie das des Handlungsreisenden zu finden, erfordert üblicherweise unvernünftig viele Schritte.

Um schnell zu brauchbaren Lösungen zu kommen, sind meist durch Heuristiken motivierte Näherungsverfahren notwendig, die aber in der Regel keine Qualitätsabschätzung für die gefundenen Lösungen liefern. Je nachdem, ob eine Heuristik eine neue Tour konstruiert oder ob sie versucht, eine bestehende Rundreise zu verbessern, wird sie als Eröffnungs- (auch Konstruktions-) oder Verbesserungsverfahren bezeichnet. Darüber hinaus gibt es Dualheuristiken, die Mindestlängen für eine Tour berechnen.

Im Hinblick auf eine mathematische Optimierung lösen gierige Algorithmen kombinatorische Probleme, die die Eigenschaften von Matroiden aufweisen, am besten. Ein Matroid ist eine mathematische Struktur, mit deren Hilfe der Begriff der Unabhängigkeit aus der linearen Algebra verallgemeinert wird. Es stellt einen Spezialfall der allgemeineren Unabhängigkeitssysteme dar. Matroide besitzen Anwendungen in vielen Bereichen der Kombinatorik, insbesondere der kombinatorischen Optimierung, sowie der Graphentheorie.

Minima

Beim Problem des Handlungsreisenden lassen sich auf einfache Weise untere Schranken herausfinden. Sie geben die minimale Länge einer Tour und somit die minimalen Kosten einer entsprechenden Lösung an. Was würde passieren, wenn eine Kante bzw. Knotenverbindung gestrichen würde, etwa in einem Grenzkonflikt oder durch den Brexit? Es entstünde ein „minimal aufspannender Baum“, also ein Teilgraph, der alle Knoten, aber keine Kreise enthält (also ein aufspannender Baum mit minimaler Summe der Kantenlängen) und der sich leicht bestimmen ließe.

Der Dijkstra-Algorithmus kann als eine auf dem Greedy-Prinzip basierende Weiterentwicklung der Breitensuchen für gewichtete Kanten aufgefasst werden. Allerdings funktioniert diese Weiterentwicklung nur für nichtnegative Gewichte. Es geht also um Knoten und Beziehungen, was eigentlich das Feld von Graphen ist. Dieser Algorithmus ist nachprüfbar optimal für die Graphsuche und das Finden des kürzesten Pfads.

Verfahren

Pro Knoten wird der Distanzwert D zum Startknoten in einer Prioritätswarteschlange Q gespeichert. Zu Beginn ist für den Startknoten 0 und für alle anderen Knoten unendlich ∞ eingetragen.

Schleifendurchlauf: Der erste Knoten k1 wird aus der Warteschlange Q genommen. Der endgültige Distanzwert von k1 ist das aktuelle D. Nun wird Q verändert. Bei allen Knoten ki, die direkte Nachbarn von k1 sind, wird nun überprüft, ob das aktuelle D größer ist als D(k1) + das Gewicht der Kante k1ki. Also wenn D(ki) > (D(k1) + k1ki), dann D(ki) = D(k1) + k1ki.

Ein weiterer Ansatz für die Minimumsuche stellt der Algorithmus von Prim dar. Er dient zum Finden des kleinsten aufspannenden Baums (s. o.):

Wähle einen beliebigen Knoten als Startgraph T.

Solange T noch nicht alle Knoten enthält, suche eine Kante minimalen Gewichts, die einen Knoten, der nicht in T ist, mit T verbindet und füge diese Kante und den damit verbundenen Knoten zu T hinzu.

Achtung: Das zugrundeliegende Mengensystem – die Menge der Bäume – ist aber kein Unabhängigkeitssystem. Ein Unabhängigkeitssystem ist in der Kombinatorik eine Verallgemeinerung der mathematische Struktur des Matroides. Ein Unabhängigkeitssystem ( E , U ) besteht aus einer endlichen Grundmenge E und einem darüber definierten nicht leeren Mengensystem U, das bezüglich der Teilmengen-Bildung abgeschlossen ist.

Auch der Algorithmus von Kruskal dient dem Finden des kleinsten aufspannenden Baums. Die Grundidee besteht darin, die Kanten in der Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zu wählen, die mit allen zuvor gewählten Kanten keinen Kreis schließt.

Vorgehensweise

Die Menge der Kanten werden sortiert in einer Liste L gespeichert.

Wähle die erste Kante in L als Startgraph T und lösche sie aus der Liste.

Solange T noch nicht alle Knoten enthält, gehe L der Reihe nach durch. Füge die erste Kante in T ein, die keinen Kreis mit den Kanten, die bereits in T liegen, bilden. Die gewählte Kante und die Kanten, die einen Kreis bilden, können aus L gelöscht werden.

In der englischen Wikipedia findet man ein animiertes Beispiel und zahlreiche Beispiele.

Weitere Anwendungsbereiche sind zum Beispiel Entscheidungsbäume und die Kodierung mit dem Huffman-Verfahren. Auch das klassische Rucksackproblem ist ein Problem der kombinatorischen Optimierung.

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 6

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

Grundlagen Statistik & Algorithmen, Teil 7

So deckt der Local Outlier Factor Anomalien auf

(ID:46004042)