Was ist ein greedy Algorithmus und in welchen Fällen wird er angewendet?
sobes.tech KI
Antwort von AI
Der greedy-Algorithmus ist ein Ansatz zur Lösung von Optimierungsproblemen, bei dem jeder Schritt die beste lokale Lösung (die vorteilhafteste Option im aktuellen Moment) auswählt, in der Hoffnung, dass diese Sequenz optimaler lokaler Lösungen zu einer global optimalen Lösung führt. Er berücksichtigt nicht die möglichen Folgen der aktuellen Wahl für die zukünftigen Schritte.
Eigenschaften:
- Einfachheit: In der Regel einfacher zu implementieren als dynamische Programmierung oder andere Optimierungsmethoden.
- Geschwindigkeit: Hat oft eine geringere rechnerische Komplexität.
- Optimale Garantie: Garantiert nicht immer die Auffindung der global optimalen Lösung. Die Garantie gilt nur für bestimmte Problemklassen.
Wird bei Problemen angewendet, bei denen nachgewiesen wurde, dass die lokal optimale Wahl in jedem Schritt zu einer global optimalen Lösung führt. Beispiele:
- Aktivitätsauswahlproblem: Auswahl der maximalen Anzahl nicht überlappender Aktivitäten.
- Rucksackproblem (bei Bruchbarkeit der Gegenstände): Wenn Gegenstände teilbar sind. Andernfalls ist es ein Problem der dynamischen Programmierung.
- Prim- und Kruskal-Algorithmus: Zur Suche des minimalen Spannbaums in einem Graphen.
- Dijkstra-Algorithmus: Zur Suche des kürzesten Pfads in einem Graphen mit nicht-negativen Kantengewichten.
- Huffman-Codierung: Zur Konstruktion eines optimalen Präfix-Codes.
Beispiel für Pseudocode für den Aktivitätsauswahlalgorithmus:
Funktion WähleAktivitäten(aktivitäten):
Sortiere aktivitäten nach Endzeit
ausgewählte_aktivitäten = leere Liste
letzte_endzeit = 0
Für jede aktivität in aktivitäten:
Wenn aktivität.startzeit >= letzte_endzeit:
Füge aktivität zu ausgewählte_aktivitäten hinzu
letzte_endzeit = aktivität.endzeit
Rückgabe ausgewählte_aktivitäten
Es ist wichtig zu prüfen, ob der greedy-Algorithmus für ein bestimmtes Problem anwendbar ist, da er sonst eine suboptimale Lösung liefern kann.
# Einfaches Beispiel, bei dem der greedy-Algorithmus nicht optimal ist
# Münzwechselproblem: möglichst wenige Münzen ausgeben
# Verfügbare Münzen: [1, 5, 10, 25] USD
# Beispiel: 30 Cent
# Greedy-Algorithmus:
# Nimmt die größte Münze <= 30 (25) -> Rest 5
# Nimmt die größte Münze <= 5 (5) -> Rest 0
# Ergebnis: 2 Münzen (25 + 5). Hier ist es optimal.
# Verfügbare Münzen: [1, 6, 10]
# Beispiel: 12 Cent
# Greedy-Algorithmus:
# Nimmt die größte Münze <= 12 (10) -> Rest 2
# Nimmt die größte Münze <= 2 (1) -> Rest 1
# Nimmt die größte Münze <= 1 (1) -> Rest 0
# Ergebnis: 3 Münzen (10 + 1 + 1).
# Die optimale Lösung wären 2 Münzen (6 + 6).
# Dieses Beispiel zeigt, dass der greedy-Algorithmus nicht immer zur global optimalen Lösung führt,
# wenn die Eigenschaften des Problems nicht mit seiner Anwendung übereinstimmen (z.B.,
# bei beliebigen Nominalen, die oft vom greedy-Algorithmus profitieren,
# aber nicht bei willkürlichen Nominalen).