In diesem Tutorial erfahren Sie, was ein Greedy-Algorithmus ist. Außerdem finden Sie ein Beispiel für einen gierigen Ansatz.
Ein gieriger Algorithmus ist ein Ansatz zur Lösung eines Problems, indem die derzeit beste verfügbare Option ausgewählt wird, ohne sich um das zukünftige Ergebnis sorgen zu müssen. Mit anderen Worten, die lokal besten Entscheidungen zielen darauf ab, global beste Ergebnisse zu erzielen.
Dieser Algorithmus ist möglicherweise nicht die beste Option für alle Probleme. In einigen Fällen kann dies zu falschen Ergebnissen führen.
Dieser Algorithmus kehrt niemals zurück, um die getroffene Entscheidung umzukehren. Dieser Algorithmus arbeitet von oben nach unten.
Der Hauptvorteil dieses Algorithmus ist:
- Der Algorithmus ist einfacher zu beschreiben .
- Dieser Algorithmus kann eine bessere Leistung als andere Algorithmen erzielen (jedoch nicht in allen Fällen).
Machbare Lösung
Eine praktikable Lösung ist diejenige, die die optimale Lösung für das Problem bietet.
Gieriger Algorithmus
- Zunächst ist der Lösungssatz (der Antworten enthält) leer.
- Bei jedem Schritt wird ein Element zum Lösungssatz hinzugefügt.
- Wenn der Lösungssatz machbar ist, wird der aktuelle Artikel beibehalten.
- Andernfalls wird der Artikel abgelehnt und nie wieder berücksichtigt.
Beispiel - Gieriger Ansatz
Problem: Sie müssen einen Betrag mit der kleinstmöglichen Anzahl von Münzen ändern. Betrag: $ 28 Verfügbare Münzen: $ 5 Münze $ 2 Münze $ 1 Münze
Lösung:
- Erstellen Sie eine leere Lösungsmenge = ().
- Münzen = (5, 2, 1)
- Summe = 0
- Während die Summe ≠ 28 ist, gehen Sie wie folgt vor.
- Wählen Sie eine Münze C aus Münzen aus, so dass Summe + C <28.
- Wenn C + Summe> 28 ist, wird keine Lösung zurückgegeben.
- Sonst ist Summe = Summe + C.
- Fügen Sie C zum Lösungssatz hinzu.
Bis zu den ersten 5 Iterationen enthält das Lösungsset 5 5-Dollar-Münzen. Danach erhalten wir 1 $ 2 Münze und schließlich 1 $ 1 Münze.
Gierige Algorithmusanwendungen
- Auswahl Sortieren
- Rucksackproblem
- Minimum Spanning Tree
- Single Source Shortest Path Problem
- Job Scheduling Problem
- Prims minimaler Spanning Tree-Algorithmus
- Kruskals Minimal Spanning Tree-Algorithmus
- Dijkstras Minimal Spanning Tree-Algorithmus
- Huffman-Codierung
- Ford-Fulkerson-Algorithmus
