Gieriger Algorithmus

Was bedeutet “gieriger Algorithmus”?

Ein gieriger Algorithmus (engl. :”greedy Alogrithm”) ist eine algorithmische Strategie, die in jeder kleinen Phase die bestmögliche Wahl trifft, mit dem Ziel, dass dies schließlich zu einer global optimalen Lösung führt. Das bedeutet, dass der Algorithmus ohne Rücksicht auf die Konsequenzen die momentan beste Lösung wählt. Er wählt das beste unmittelbare Ergebnis aus, berücksichtigt aber nicht das Gesamtbild, weshalb er als gierig gilt.

Techopedia erklärt den Greedy-Algorithmus

Ein gieriger 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 (siehe auch: “Automatisierung“). Er hofft nur, dass der eingeschlagene Weg das globale Optimum ist, aber es hat sich immer wieder gezeigt, dass diese Methode nicht oft zu einer global optimalen Lösung führt. Es ist sogar durchaus möglich, dass die besten kurzfristigen Lösungen zu den schlechtesten globalen Ergebnissen führen.

Stellen Sie sich vor, Sie würden in einem Produktionsbetrieb viele Abkürzungen nehmen: Kurzfristig werden große Mengen an Herstellungskosten eingespart, aber dies führt letztendlich zum Untergang, da die Qualität beeinträchtigt wird, was zu Produktrückgaben und geringen Umsätzen führt, da die Kunden sich mit dem “billigen” Produkt vertraut machen. Dies ist jedoch nicht immer der Fall. Es gibt viele Anwendungen, bei denen der Gieralgorithmus am besten geeignet ist, um eine global optimale Lösung zu finden oder sich dieser anzunähern, z. B. bei der Erstellung eines Huffman-Baums oder eines Entscheidungs-Lernbaums.

Ein Beispiel: Nehmen Sie den Pfad mit der größten Gesamtsumme. Ein gieriger Algorithmus würde aufgrund der Kurzsichtigkeit den blauen Pfad wählen und nicht den orangenen, 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 sie bestimmt, 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