Gierige Algorithmen und wann sie funktionieren

Code in:JavaC#PythonJavaScript

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:

function book(requests, rule) {
  const taken = [];
  for (const [start, end] of [...requests].sort(rule)) {
    if (taken.every(([s, e]) => end <= s || e <= start)) {
      taken.push([start, end]);
    }
  }
  return taken;
}

function show(rule, taken) {
  const slots = taken.map(([s, e]) => `${s}–${e}`).join(", ");
  console.log(`${rule}: ${slots} (${taken.length})`);
}

show("Nach Beginn", book(requests, (a, b) => a[0] - b[0]));
show("Nach Länge", book(requests, (a, b) => (a[1] - a[0]) - (b[1] - b[0])));
show("Nach Ende", book(requests, (a, b) => a[1] - b[1]));

Ausgabe

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

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

[...requests].sort(...) sortiert eine Kopie, und const [start, end] entpackt jedes Paar.

const requests = [
  [8, 16], [12, 15], [9, 12], [15, 18],
  [11, 13], [17, 20], [14, 16], [18, 20],
];
const taken = maxMeetings(requests);
for (const [start, end] of taken) console.log(`${start}–${end}`);
console.log(`Besprechungen: ${taken.length}`);

Ausgabe

9–12
12–15
15–18
18–20
Besprechungen: 4

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

Schritt für Schritt, in Worten

1. 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.
2. Die orangefarbene Linie zeigt, ab wann der Raum frei ist. Am Anfang ist nichts belegt: frei ab 0.
3. Anfrage 1 (9–12) beginnt um 9, der Raum ist ab 0 frei: nimm sie an. Jetzt ist der Raum bis 12 belegt.
4. Anfrage 2 (11–13) beginnt um 11, vor 12: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
5. Anfrage 3 (12–15) beginnt um 12, der Raum ist ab 12 frei: nimm sie an. Jetzt ist der Raum bis 15 belegt.
6. Anfrage 4 (8–16) beginnt um 8, vor 15: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
7. Anfrage 5 (14–16) beginnt um 14, vor 15: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
8. Anfrage 6 (15–18) beginnt um 15, der Raum ist ab 15 frei: nimm sie an. Jetzt ist der Raum bis 18 belegt.
9. Anfrage 7 (17–20) beginnt um 17, vor 18: Sie überschneidet sich mit einer schon angenommenen Besprechung, lehne sie ab.
10. Anfrage 8 (18–20) beginnt um 18, der Raum ist ab 18 frei: nimm sie an. Jetzt ist der Raum bis 20 belegt.
11. 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.

Array.prototype.sort ist seit ES2019 stabil. Ohne Vergleichsfunktion sortiert es als Text: [9, 12].sort() liefert [12, 9].

Probier es aus

Finde den Fehler

Ein Kollege hat den gierigen Algorithmus kopiert und bekam nur drei Besprechungen:

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start > freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

const requests = [
  [8, 16], [12, 15], [9, 12], [15, 18],
  [11, 13], [17, 20], [14, 16], [18, 20],
];
const taken = maxMeetings(requests);
for (const [start, end] of taken) console.log(`${start}–${end}`);
console.log(`Besprechungen: ${taken.length}`);

Ausgabe

9–12
14–16
17–20
Besprechungen: 3

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1function maxMeetings(requests) {2 const byEnd = [...requests].sort((a, b) => a[1] - b[1]);3 const taken = [];4 let freeFrom = 0;5 for (const [start, end] of byEnd) {6 if (start > freeFrom) {7 taken.push([start, end]);8 freeFrom = end;9 }10 }11 return taken;12}

Prüfen

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

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if () {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

Prüfen

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.

const COINS = [200, 100, 50, 20, 10, 5, 2, 1];

function change(cents) {
  const given = [];
  for (const coin of COINS) {
    while (cents >= coin) {
      given.push(coin);
      cents -= coin;
    }
  }
  return given;
}

function pay(cents) {
  const given = change(cents);
  console.log(`${cents} Cent: ${given.join(" ")} (${given.length} Münzen)`);
}

pay(485);

Ausgabe

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

const COINS = [200, 100, 50, 20, 10, 5, 2, 1];

function change(cents) {
  const given = [];
  for (const coin of COINS) {
    while (cents >= coin) {
      given.push(coin);
      cents -= coin;
    }
  }
  return given;
}

function pay(cents) {
  const given = change(cents);
  console.log(`${cents} Cent: ${given.join(" ")} (${given.length} Münzen)`);
}

pay(99);

Antwort

99 Cent: 50 20 20 5 2 1 1 (7 Münzen)

99 Cent: 20 20 20 20 10 5 2 2 (8 Münzen)

99 Cent: 50 20 20 5 2 2 (6 Münzen)

Prüfen

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

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  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:

Ausgabe

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

Teste dich

1. Was macht einen Algorithmus „gierig“?

Bei jedem Schritt nimmt er die im Moment beste Wahl und überdenkt sie nieEr hält eine Tabelle mit den Antworten auf die kleineren AufgabenEr probiert jede Möglichkeit und behält die beste

2. Warum werden die Raumanfragen nach Ende sortiert und nicht nach Beginn?

Weil das Sortieren nach Ende kürzere Besprechungen ergibtDie Besprechung, die am frühesten endet, lässt den meisten Rest des Tages für die anderenWeil sich nach Beginn nicht sortieren lässt

3. Überschneiden sich die Anfragen 9–12 und 12–15?

Nein: Die erste endet genau, wenn die zweite beginnt, deshalb lautet die Prüfung >=Ja: Beide enthalten 12:00 UhrDas hängt von der Sprache ab

4. Was zeigt das Austauschargument?

Dass gierig schneller ist als jede TeilmengeDie erste Besprechung jedes besten Plans lässt sich gegen die gierige Wahl austauschen, ohne dass die Anzahl sinktDass jeder gierige Algorithmus richtig ist

5. Wechselgeld in Euro-Münzen ist gierig. Wann geht dieselbe Regel schief?

Nie: Die größte Münze zuerst ist immer am bestenNur bei Beträgen über 5 €Mit Münzen zu 1, 3 und 4 Cent: Für 6 Cent liefert gierig 4 + 1 + 1, und am wenigsten sind 3 + 3

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Union-Find · Minimaler Spannbaum · Überlappende Teilprobleme · Das Wechselgeldproblem
• Geht weiter in: Wann ein gieriger Algorithmus scheitert
• Aufgaben zum Thema: Gierige Algorithmen