Greedy-Algorithmen
Was macht einen Algorithmus gierig?
Ein gieriger Algorithmus erstellt Schritt für Schritt eine Lösung und wählt immer die Option aus, die im Moment am besten aussieht – ohne frühere Entscheidungen zu überdenken. Kein Zurückweichen, kein Blick nach vorne.
Es funktioniert, wenn zwei Eigenschaften gelten:
- Greedy-Choice-Eigenschaft – eine lokal optimale Wahl führt zu einer global optimalen Lösung.
- Optimale Unterstruktur – das verbleibende Problem nach jeder Auswahl ist eine kleinere Instanz desselben Problems.
Aktivitätsauswahl – Das klassische Beispiel
Wählen Sie anhand einer Reihe von Aktivitäten mit Start- und Endzeiten die maximale Anzahl sich nicht überschneidender Aktivitäten aus.
Gierige Strategie: Sortieren Sie nach Endzeit und wählen Sie immer die Aktivität aus, die am frühesten endet.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
Warum funktioniert das? Die Auswahl der Aktivität, die am frühesten abgeschlossen wird, lässt den meisten Spielraum für zukünftige Aktivitäten. Keine andere Wahl kann es besser machen.
Huffman-Codierung – Konzept
Erstellen Sie einen optimalen präfixfreien Binärcode, indem Sie die zwei Symbole mit der niedrigsten Häufigkeit wiederholt zusammenführen. Das ist gierig: Bei jedem Schritt wird das günstigste Paar zusammengeführt. Das Ergebnis ist ein Baum, in dem häufige Symbole Kurzcodes erhalten.
Sprungspiel
Bestimmen Sie anhand eines Arrays, bei dem nums[i] die maximale Sprunglänge vom Index i ist, ob Sie den letzten Index erreichen können.
Gieriger Ansatz: Verfolgen Sie den bisher am weitesten entfernten Index. Von links nach rechts scannen – wenn Sie jemals ins Hintertreffen geraten, geben Sie „false“ zurück.
Diskussion
Anmelden an der Diskussion teilnehmen