Kurs:Algorithmen und Datenstrukturen/Vorlesung/Greedyalgorithmen
Greedyalgorithmus Bearbeiten
Auf dieser Seite wird der Greedyalgorithmus behandelt.
Greedy bedeutet "gierig". Der Algorithmus erfolgt nach dem Prinzip, dass versucht wird mit jedem Teilschritt so viel wie möglich zu erreichen. Greedy-Algorithmen (gierige Algorithmen) zeichnen sich dadurch aus, dass sie immer denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht.
Lokales Optimum Bearbeiten
Der Greedy Algorithmus berechnet in jedem Schritt das lokale Optimum, dabei kann jedoch das globale Optimum verfehlt werden.
Jedoch entspricht in vielen Fällen das lokale Optimum auch dem globalem Optimum, bzw. es reicht ein lokales Optimum aus.
Problemklasse Bearbeiten
- Gegebene Menge von Eingabewerten
- Menge von Lösungen, die aus Eingabewerten aufgebaut sind
- Lösungen lassen sich schrittweise aus partiellen Lösungen, beginnend bei der leeren Lösung, durch Hinzunahme von Eingabewerten aufbauen. Alternativ: bei einer ganzen Menge beginnend schrittweise jeweils ein Element wegnehmen
- Bewertungsfunktion für partielle und vollständige Lösungen
- Gesucht wird die/eine optimale Lösung
