Gieriger Algorithmus

Definition - Was bedeutet Greedy-Algorithmus?

Ein gieriger Algorithmus ist eine algorithmische Strategie, die in jeder kleinen Phase die beste optimale Wahl trifft, mit dem Ziel, dass dies letztendlich zu einer global optimalen Lösung führt. Dies bedeutet, dass der Algorithmus derzeit die beste Lösung auswählt, ohne Rücksicht auf die Konsequenzen. Es wählt die beste sofortige Ausgabe aus, berücksichtigt jedoch nicht das Gesamtbild und wird daher als gierig angesehen.

Technische.me erklärt den Greedy-Algorithmus

Ein gieriger Algorithmus wählt in jedem Schritt die bestmögliche Antwort und fährt dann mit dem nächsten Schritt fort, bis er das Ende erreicht, ohne Rücksicht auf die Gesamtlösung. Sie hofft nur, dass der eingeschlagene Weg der global optimale ist, aber wie sich immer wieder gezeigt hat, liefert diese Methode nicht oft eine global optimale Lösung. Tatsächlich ist es durchaus möglich, dass die optimalsten kurzfristigen Lösungen zu einem möglichst schlechten globalen Ergebnis führen.

Stellen Sie sich das als eine Menge Abkürzungen in einem Fertigungsunternehmen vor: Kurzfristig werden große Mengen an Herstellungskosten eingespart, aber dies führt letztendlich zu einem Rückgang, da die Qualität beeinträchtigt wird, was zu Produktrenditen und geringen Umsätzen führt, wenn Kunden mit dem Produkt vertraut werden "Billiges" Produkt. Dies ist jedoch 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 zu approximieren, z. B. beim Erstellen eines Huffman-Baums oder eines Entscheidungslernbaums.

Zum Beispiel: Nehmen Sie den Pfad mit der größten Gesamtsumme. Ein gieriger Algorithmus würde aufgrund von Kurzsichtigkeit eher den blauen Pfad als den orangefarbenen Pfad nehmen, der die größte Summe ergibt.

Komponenten:

  • Ein Kandidatendatensatz, 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 einen Beitrag zur Lösung leisten kann
  • Eine Zielfunktion, die einer Teillösung einen Wert zuweist
  • Eine Lösungsfunktion, die anzeigt, dass die optimale Lösung gefunden wurde