Gierige Algorithmen und wann sie funktionieren
Kurz gesagt: Ein gieriger Algorithmus nimmt bei jedem Schritt die im Moment beste Wahl und geht nie zurück; er liefert die optimale Antwort nur bei Problemen, bei denen diese Wahl sicher ist, was einen Beweis wie das Austauschargument braucht.
Problem
Der Besprechungsraum
Der Coworking-Space hat einen Besprechungsraum. Für morgen sind acht Anfragen eingegangen, jede mit einer Anfangs- und einer Endstunde. Zwei Besprechungen, die sich überschneiden, können nicht gleichzeitig im Raum sein. Du willst möglichst viele Teams annehmen: Jedes Team, das du abweist, geht zur Konkurrenz.
Die ersten Ideen sind einfache Regeln: die früheste Anfrage zuerst oder die kürzeste zuerst (kürzere brauchen weniger Zeit). Du sortierst nach der Regel und nimmst jede Anfrage an, die sich nicht mit den schon angenommenen überschneidet:
static List<int[]> Book(int[][] requests, Func<int[], int> rule){ var taken = new List<int[]>(); foreach (var r in requests.OrderBy(rule)) { bool free = taken.All(t => r[1] <= t[0] || t[1] <= r[0]); if (free) taken.Add(r); } return taken;}
static void Show(string rule, List<int[]> taken){ var slots = string.Join(", ", taken.Select(t => $"{t[0]}–{t[1]}")); Console.WriteLine($"{rule}: {slots} ({taken.Count})");}Show("Nach Beginn", Book(requests, r => r[0]));Show("Nach Länge", Book(requests, r => r[1] - r[0]));Show("Nach Ende", Book(requests, r => r[1]));Nach Beginn: 8–16, 17–20 (2)Nach Länge: 11–13, 14–16, 18–20 (3)Nach Ende: 9–12, 12–15, 15–18, 18–20 (4)Nach Beginn ergibt 2 Besprechungen, nach Länge 3 und nach Ende 4. Ist 4 das Meiste? Probiere alle 2⁸ = 256 Teilmengen: ja, 5 passen nicht. Aber warum gerade die Regel „nach Ende“, und wie kann man sicher sein, ohne alles zu probieren?
Die Idee
Ein gieriger Algorithmus
Ein gieriger (Greedy-)Algorithmus trifft die Wahl, die jetzt am besten aussieht, und kommt nie zurück, um sie zu überdenken. Es gibt keine Tabelle wie bei der dynamischen Programmierung und kein Probieren jeder Möglichkeit: meist eine Sortierung und ein Durchlauf.
Für den Raum heißt gierig: die Anfragen nach Ende sortieren und jede annehmen, die nicht früher beginnt als der Moment, in dem der Raum frei wird. Eine Variable, freeFrom, hält diesen Moment, damit du nicht mit jeder schon angenommenen Besprechung vergleichen musst.
Die drei Regeln aus dem Problem sind alle gierig. Der Unterschied ist, was sie als „jetzt am besten“ zählen, und nur eine von ihnen ist richtig. Gierig ist schnell und einfach, kommt aber ohne Garantie: Jede gierige Regel braucht ein Argument, dass die Wahl im Moment die Zukunft nicht verdirbt.
Sieh es dir an
Gierig nach Ende
static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] >= freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}OrderBy(r => r[1]) liefert die Anfragen nach Ende, ohne das Array requests anzufassen.int[][] requests =[ [8, 16], [12, 15], [9, 12], [15, 18], [11, 13], [17, 20], [14, 16], [18, 20],];var taken = MaxMeetings(requests);foreach (var t in taken) Console.WriteLine($"{t[0]}–{t[1]}");Console.WriteLine($"Besprechungen: {taken.Count}");9–1212–1515–1818–20Besprechungen: 4static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] >= freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}Schritt für Schritt, in Worten
- Acht Anfragen für einen Besprechungsraum, in der Reihenfolge, in der sie kamen. Sortiere sie nach Ende: Zuerst kommt die, die am frühesten endet.
- Die orangefarbene Linie zeigt, ab wann der Raum frei ist. Am Anfang ist nichts belegt: frei ab 0.
- Anfrage 1 (9–12) beginnt um 9, der Raum ist ab 0 frei: nimm sie an. Jetzt ist der Raum bis 12 belegt.
- Anfrage 2 (11–13) beginnt um 11, vor 12: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
- Anfrage 3 (12–15) beginnt um 12, der Raum ist ab 12 frei: nimm sie an. Jetzt ist der Raum bis 15 belegt.
- Anfrage 4 (8–16) beginnt um 8, vor 15: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
- Anfrage 5 (14–16) beginnt um 14, vor 15: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
- Anfrage 6 (15–18) beginnt um 15, der Raum ist ab 15 frei: nimm sie an. Jetzt ist der Raum bis 18 belegt.
- Anfrage 7 (17–20) beginnt um 17, vor 18: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
- Anfrage 8 (18–20) beginnt um 18, der Raum ist ab 18 frei: nimm sie an. Jetzt ist der Raum bis 20 belegt.
- 4 Besprechungen: 9–12, 12–15, 15–18, 18–20. Jede angenommene endet am frühesten von den übrigen, also lässt sie den meisten Rest des Tages für die anderen.
Jede angenommene Besprechung lässt den Raum so früh wie möglich frei. Die abgelehnten sind kein Verlust: Jede von ihnen überschneidet sich mit einer Besprechung, die nicht später endet als sie.
Genauer, für Neugierige
Enden zwei Anfragen zur selben Stunde, ändert die Reihenfolge zwischen ihnen die Anzahl nicht: Sobald die erste angenommen ist, beginnt die zweite vor ihrem Ende. Die eingebaute Sortierung ist in allen vier Sprachen stabil (gleiche Elemente bleiben in der Reihenfolge, in der sie kamen), also ist die Ausgabe überall gleich.
OrderBy ist stabil. Array.Sort und List.Sort sind es nicht: Bei gleichen Enden kann die andere Reihenfolge herauskommen.Probier es aus
Finde den Fehler
Ein Kollege hat den gierigen Algorithmus kopiert und bekam nur drei Besprechungen:
static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] > freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}int[][] requests =[ [8, 16], [12, 15], [9, 12], [15, 18], [11, 13], [17, 20], [14, 16], [18, 20],];var taken = MaxMeetings(requests);foreach (var t in taken) Console.WriteLine($"{t[0]}–{t[1]}");Console.WriteLine($"Besprechungen: {taken.Count}");9–1214–1617–20Besprechungen: 3In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Die Besprechung 9–12 gibt den Raum um 12 frei, und 12–15 kann genau dann beginnen. Mit dem strengen > werden direkt aufeinanderfolgende Besprechungen abgelehnt. Richtig ist if (r[0] >= freeFrom).
Die Idee
Warum nach Ende richtig ist: das Austauschargument
Nimm einen beliebigen besten Plan, zum Beispiel mit 4 Besprechungen. Sortiere seine Besprechungen nach Zeit. Gierig nimmt zuerst die Anfrage, die von allen am frühesten endet, sagen wir 9–12.
- Die erste Besprechung des besten Plans endet nicht früher als 12, weil 12 das früheste Ende von allen ist.
- Tausche sie gegen 9–12. Die anderen Besprechungen des Plans beginnen nach dem Ende der alten ersten, also auch nach 12: Nichts überschneidet sich, und die Anzahl ist dieselbe.
- Jetzt beginnen beide Pläne gleich. Entferne 9–12 und die Anfragen, die sich damit überschneiden, und wiederhole dasselbe für den Rest.
Schritt für Schritt verwandelst du den besten Plan in den gierigen, ohne eine einzige Besprechung zu verlieren. Der gierige Plan ist also mindestens so gut wie der beste: Er ist der beste.
Dasselbe Argument scheitert bei den anderen zwei Regeln. Nach Beginn kommt 8–16 zuerst: Setz es an die Stelle der ersten Besprechung, und es sperrt den Raum bis 16, und die anderen Besprechungen passen nicht mehr.
Genauer, für Neugierige
Formal ist das Argument eine Induktion über die Zahl der angenommenen Besprechungen: Nach k Schritten gibt es einen besten Plan, der mit den ersten k gierigen Wahlen beginnt. So beweist man üblicherweise einen gierigen Algorithmus: „Die gierige Wahl ist sicher“ (es gibt eine beste Lösung, die sie enthält) plus „optimale Teilstruktur“ (der Rest ist dieselbe Aufgabe, nur kleiner). Die zweite Eigenschaft teilt er mit der dynamischen Programmierung. Die erste fehlt, wenn gierig scheitert.
Probier es aus
Ergänze die Bedingung
static List<int[]> MaxMeetings(int[][] requests)
{
var taken = new List<int[]>();
int freeFrom = 0;
foreach (var r in requests.OrderBy(r => r[1]))
{
if ()
{
taken.Add(r);
freeFrom = r[1];
}
}
return taken;
}Eine Anfrage wird angenommen, wenn sie nicht früher beginnt als der Moment, in dem der Raum frei wird: r[0] >= freeFrom.
Die Idee
Ein zweites Beispiel: Wechselgeld in Euro
Die Kasse des Shops gibt Wechselgeld mit möglichst wenigen Münzen. Die Euro-Münzen sind 2 €, 1 €, 50, 20, 10, 5, 2 und 1 Cent. Gierig: Gib die größte Münze, die noch in den Rest passt.
static List<int> Change(int cents){ int[] coins = [200, 100, 50, 20, 10, 5, 2, 1]; var given = new List<int>(); foreach (int coin in coins) { while (cents >= coin) { given.Add(coin); cents -= coin; } } return given;}
static void Pay(int cents){ var given = Change(cents); Console.WriteLine($"{cents} Cent: {string.Join(" ", given)} ({given.Count} Münzen)");}Pay(485);485 Cent: 200 200 50 20 10 5 (6 Münzen)Bei den Euro-Münzen ergibt das für jeden Betrag die wenigsten Münzen: Es wurde gegen die Wechselgeldtabelle für jeden Betrag bis 5 € geprüft. Die Münzen wurden absichtlich so gewählt.
Die Regel „größte zuerst“ stimmt aber nicht für beliebige Münzen. Mit Münzen zu 1, 3 und 4 Cent liefert gierig für 6 Cent 4 + 1 + 1, drei Münzen, und zwei genügen: 3 + 3. Ein Zeichen, das man auf einen Blick sieht, gibt es nicht: Auch bei Münzen, die jeweils mindestens doppelt so groß sind wie die nächste, kann gierig scheitern. Mit 1, 4 und 9 Cent liefert es für 12 Cent 9 + 1 + 1 + 1, und 4 + 4 + 4 genügt. Wie man solche Fälle sucht, steht in der nächsten Lektion.
Probier es aus
Sage die Ausgabe voraus
static List<int> Change(int cents){ int[] coins = [200, 100, 50, 20, 10, 5, 2, 1]; var given = new List<int>(); foreach (int coin in coins) { while (cents >= coin) { given.Add(coin); cents -= coin; } } return given;}
static void Pay(int cents){ var given = Change(cents); Console.WriteLine($"{cents} Cent: {string.Join(" ", given)} ({given.Count} Münzen)");}
Pay(99);Die Idee
Ein drittes Beispiel: Kruskal
Ein Internetanbieter verbindet Stadtviertel mit Glasfaserkabel. Jedes verlegte Kabel hat einen Preis, und das Ziel ist, dass alle Viertel für möglichst wenig Geld verbunden sind. Das ist der minimale Spannbaum, und Kruskal baut ihn gierig: Er sortiert die möglichen Kabel nach Preis und nimmt jeweils das nächstbilligste, es sei denn, es schließt einen Kreis (die zwei Viertel sind schon verbunden). Wer mit wem verbunden ist, hält Union-Find.
Auch hier ist das Argument ein Austausch: Enthält der beste Baum das billigste Kabel zwischen zwei Gruppen nicht, setz es ein und entferne das teurere Kabel aus dem Kreis, der sich schließt. Der Preis steigt nicht.
Genauer, für Neugierige
Auch andere bekannte Algorithmen sind gierig. Dijkstra nimmt immer den nächsten noch nicht bearbeiteten Knoten und überdenkt ihn nie, und das ist richtig, weil Wege keine negativen Längen haben. Die Huffman-Kodierung (hinter ZIP und JPEG) verschmilzt immer die zwei seltensten Symbole. Sie haben eins gemeinsam: Jeder hat einen Beweis, dass die Wahl im Moment sicher ist.
Sieh es dir an
Was es kostet
Gierig ist eine Sortierung, O(n log n), und ein Durchlauf, O(n). Jede Teilmenge zu probieren ist O(2ⁿ): Bei 20 Anfragen sind das über eine Million Teilmengen, bei 60 wird es nie fertig. Hier sortiert Bench mit Mergesort und zählt seine Vergleiche. Die eingebaute Sortierung deiner Sprache macht eine etwas andere Zahl, wächst aber genauso.
- Jede Teilmenge
O(2ⁿ) - Gierig nach dem Ende
O(n log n)
| Algorithmus | n = 10 | n = 20 | n = 1.000 | n = 100.000 | n = 1.000.000 |
|---|---|---|---|---|---|
| Jede Teilmenge | 1.024 | 1.048.576 | ≈ 10³⁰¹ | ≈ 10³⁰¹⁰² | ≈ 10³⁰¹⁰²⁹ |
| Gierig nach dem Ende | 33 | 85 | 9.691 | 1.636.658 | ≈ 19.639.896 |
static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] >= freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}Übung
Der Kurier
Löse die Aufgabe in deinem Editor.
Der Kurier. Ein Kurier liefert Pakete in einem Gewerbepark aus. Jeder Kunde hat gesagt, in welchem Zeitfenster er an der Adresse ist: 9–11, 10–12, 11–14, 13–15, 14–17, 16–18 und 17–19. Bei jedem Durchgang lässt der Kurier die Pakete aller da, die gerade an der Adresse sind. Wie wenige Durchgänge braucht es, und zu welchen Uhrzeiten? Schreibe den gierigen Algorithmus und gib aus:
Durchläufe bei: 11, 15, 18 (3)Hinweis: Sortiere die Fenster nach Ende. Der erste Durchgang liegt am Ende des Fensters, das am frühesten endet: Später verlierst du diesen Kunden, und früher bedienst du nicht mehr. Dann überspring alle Fenster, die diese Uhrzeit schon enthalten.
Weitere Aufgaben
- Das Argument. Schreibe das Austauschargument für den Kurier: Warum ist der erste Durchgang am Ende des frühesten Fensters nicht schlechter als der erste Durchgang der besten Lösung?
- Ein zweiter Raum. Hat der Coworking-Space zwei Räume, funktioniert „nach Ende“, wenn du jede Anfrage dem Raum gibst, der zuletzt frei wurde, aber rechtzeitig?
- Preise. Zahlen die Anfragen unterschiedliche Beträge und du willst das meiste Geld statt der meisten Besprechungen, ist gierig nach Ende nicht mehr richtig. Finde drei Anfragen, bei denen es nicht stimmt, und löse die Aufgabe mit dem Rezept der dynamischen Programmierung.
Test