Veröffentlicht · wird verbessert
Algorithm
Greedy-Algorithmen treffen in jedem Schritt die lokal beste Wahl, ohne sie zu revidieren, etwa bei Intervallplanung, Huffman-Kodierung und Bruchteil-Rucksack.
Ein Greedy-Algorithmus (gieriger Algorithmus) baut seine Lösung aus einer Folge von Entscheidungen auf: In jedem Schritt wählt er nach einer festen Regel den Kandidaten, der gerade am besten aussieht, und nimmt diese Entscheidung nie zurück. Meist werden die Kandidaten sortiert oder in eine Prioritätswarteschlange gelegt und nacheinander angenommen. Der Code ist daher kurz, und die Laufzeit liegt typischerweise bei O(n log n), bestimmt durch Sortieren oder Heap-Operationen.
Wo ein Greedy-Verfahren funktioniert, ist es die schnellste und einfachste Lösung, aber es funktioniert nicht immer. Für ein optimales Ergebnis müssen die Greedy-Auswahleigenschaft und die optimale Teilstruktur gelten, was man meist mit einem Austauschargument beweist. Schon ein einziges Gegenbeispiel, etwa der Betrag 6 mit Münzen zu 1, 3 und 4, zeigt, dass dynamische Programmierung nötig ist. Das Greedy-Prinzip steckt auch in zentralen Praxisalgorithmen wie der Huffman-Kodierung, Dijkstras kürzesten Wegen und minimalen Spannbäumen.
Beginnen Sie mit der Intervallplanung (Activity Selection) und begründen Sie mit einem Austauschargument, warum die Wahl des am frühesten endenden Termins richtig ist. Implementieren Sie danach die Huffman-Kodierung, den Bruchteil-Rucksack und die Raumzuteilung mit einem Heap. Vergleichen Sie Greedy-Ergebnisse außerdem auf kleinen Eingaben mit einer Brute-Force-Lösung; so entlarven Sie falsche Regeln im Coding-Interview am schnellsten.
Es muss eine optimale Lösung geben, die die erste gierige Wahl enthält; das ist die zentrale Bedingung für die Korrektheit.
Man zeigt, dass sich jede optimale Lösung Element für Element in die Greedy-Lösung umwandeln lässt, ohne schlechter zu werden.
Kandidaten werden nach Endzeit, Wert pro Gewicht oder Häufigkeit geordnet oder aus einem Heap entnommen, daher meist O(n log n).
Bei beliebigen Münzsystemen oder dem 0/1-Rucksackproblem liefert die Greedy-Regel falsche Ergebnisse; dann ist dynamische Programmierung gefragt.
Das Programm wählt die größte Menge sich nicht überschneidender Termine. Es sortiert die Termine nach Endzeit und nimmt einen Termin nur an, wenn er nach dem Ende des zuletzt gewählten beginnt. Das Sortieren kostet O(n log n), der Durchlauf O(n); im Beispiel werden 4 von 11 Terminen gewählt.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Greedy-Algorithmen.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Greedy-Algorithmen aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.