Was ist Greedy-Algorithmus?
Ein Greedy-Algorithmus ist eine algorithmische Strategie, die auf jeder kleinen Stufe die beste Wahl trifft, um schließlich zu einer global optimalen Lösung zu führen. Dies bedeutet, dass der Algorithmus die beste Lösung im Moment ohne Rücksicht auf Konsequenzen wählt. Es wählt die beste unmittelbare Ausgabe aus, berücksichtigt aber nicht das Gesamtbild, daher wird es als gierig betrachtet.
Ein Greedy-Algorithmus arbeitet, indem er in jedem Schritt die bestmögliche Antwort wählt und dann zum nächsten Schritt übergeht, bis er das Ende erreicht, ohne Rücksicht auf die Gesamtlösung. Es hofft nur, dass der Weg, den es nimmt, der global optimale ist, aber wie immer wieder bewiesen, ist diese Methode nicht immer eine global optimale Lösung. In der Tat ist es durchaus möglich, dass die optimalsten kurzfristigen Lösungen zu dem schlechtesten möglichen globalen Ergebnis führen.
Stellen Sie sich vor, dass es in einem Fertigungsunternehmen viele Abkürzungen gibt: Kurzfristig werden große Mengen an Herstellungskosten eingespart, doch dies führt schließlich zu einem Niedergang, da die Qualität beeinträchtigt wird, was zu Produktrücksendungen und niedrigen Umsätzen führt, wenn die Kunden mit den Produkten vertraut werden ‚Billiges‘ Produkt. Aber das ist nicht immer der Fall. Es gibt viele Anwendungen, bei denen der Greedy-Algorithmus am besten funktioniert, um die global optimale Lösung zu finden oder anzunähern, wie zum Beispiel beim Aufbau eines Huffman-Baums oder eines Entscheidungslernbaums.
Zum Beispiel: Nimm den Pfad mit der größten Gesamtsumme. Ein gieriger Algorithmus würde den blauen Pfad als Folge von Kurzsichtigkeit anstelle des orangen Pfads nehmen, der die größte Summe ergibt.
Komponenten:
– Ein Kandidatensatz von Daten, der eine Lösung benötigt
– Eine Auswahlfunktion, die den besten Beitrag zur endgültigen Lösung auswählt
– Eine Machbarkeitsfunktion, die die Auswahlfunktion unterstützt, indem ermittelt wird, ob ein Kandidat zur Lösung beitragen kann
– Eine Zielfunktion, die einer Teillösung einen Wert zuweist
– Eine Lösungsfunktion, die anzeigt, dass die optimale Lösung gefunden wurde