Ein Angebot von

Der Greedy-Algorithmus

| Autor / Redakteur: Michael Matzer / Nico Litzel

Gierige Algorithmen bestimmen z. B. die Mindestmenge an Münzen für das jeweils nötige Wechselgeld. Im Bild sind die Schritte abgebildet, die ein Mensch gehen würde, um einen gierigen Algorithmus zu imitieren, der 36 Cents herausgibt, indem er Münzen mit den Werten {1, 5, 10, 20} verwendet. Die Münze mit dem höchsten Wert, der unter dem geschuldeten Betrag liegt, ist das „lokale Optimum“.
Bildergalerie: 1 Bild
Gierige Algorithmen bestimmen z. B. die Mindestmenge an Münzen für das jeweils nötige Wechselgeld. Im Bild sind die Schritte abgebildet, die ein Mensch gehen würde, um einen gierigen Algorithmus zu imitieren, der 36 Cents herausgibt, indem er Münzen mit den Werten {1, 5, 10, 20} verwendet. Die Münze mit dem höchsten Wert, der unter dem geschuldeten Betrag liegt, ist das „lokale Optimum“. (Bild: gemeinfrei / CC0)

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 verspricht – etwa die Berechnung von Wechselgeld oder des kürzesten Wegs. Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

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.

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

Das Problem des Handlungsreisenden besteht darin, die kürzeste Strecke zu finden, die die jeweils nächstgelegenen Städte, die noch nicht besucht wurden, optimal miteinander verbindet.
Das Problem des Handlungsreisenden besteht darin, die kürzeste Strecke zu finden, die die jeweils nächstgelegenen Städte, die noch nicht besucht wurden, optimal miteinander verbindet. (Bild: gemeinfrei / CC0)

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.

Beispiel für einen „minimal aufspannenden Baum“, ein Paraboloid.
Beispiel für einen „minimal aufspannenden Baum“, ein Paraboloid. (Bild: Max paraboloid / IkamusumeFan / CC BY-SA 4.0)

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.

Das Rucksackproblem: Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.
Das Rucksackproblem: Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden. (Bild: Knapsack / Keenan Pepper / CC BY-SA 2.5)

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

Der Approximationsalgorithmus

Der Approximationsalgorithmus

11.09.19 - Für verschiedene Probleme lassen sich nur durch Annäherung bzw. Approximation optimale Lösungen finden. Durch einen geeigneten Approximationsalgorithmus versuchen Informatiker, sich dem optimalen Ergebnis anzunähern, so etwa in der Graphentheorie, die Beziehungen in Netzwerken darstellt. lesen

So deckt der Local Outlier Factor Anomalien auf

So deckt der Local Outlier Factor Anomalien auf

19.08.19 - Um Trends zu erkennen, wird oft die Clusteranalyse herangezogen. Für manche Zwecke ist es aber aufschlussreicher, Ausreißer zu untersuchen, denn sie bilden die Antithese zum „Normalen“, etwa im Betrugswesen. Der Local-Outlier-Factor-Algorithmus (LOF) ist in der Lage, den Abstand von Ausreißern zu ihren Nachbarn zu berechnen und deckt so Anomalien auf. lesen

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

23.07.19 - Der k-Means-Algorithmus ist ein Rechenverfahren, das sich für die Gruppierung von Objekten, die sogenannte Clusteranalyse, einsetzen lässt. Dank der effizienten Berechnung der Clusterzentren und dem geringen Speicherbedarf eignet sich der Algorithmus sehr gut für die Analyse großer Datenmengen, wie sie im Big-Data-Umfeld üblich sind, so etwa in der Bildverarbeitung und in der Kundensegmentierung. lesen

Der Rete-Algorithmus: Speed für Mustererkennung

Der Rete-Algorithmus: Speed für Mustererkennung

02.07.19 - Geschäftsregeln halten zahlreiche Unternehmensprozesse am Laufen, deshalb können sie mitunter sehr umfangreich werden. Der Umfang macht ihre Ausführung zeitaufwendig, weshalb jede Methode, sie zu beschleunigen, willkommen ist. Der Rete-Algorithmus beschleunigte 1979 die damals bestehenden Systeme für die Verarbeitung von Business Rules um den Faktor 3.000. Er ist bis heute die Grundlage zahlreicher Expertensysteme, etwa in der Mustererkennung. lesen

Kommentar zu diesem Artikel abgeben

Schreiben Sie uns hier Ihre Meinung ...
(nicht registrierter User)

Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
Kommentar abschicken
copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Kontaktieren Sie uns über: support.vogel.de/ (ID: 46146755 / Implementierung)