Union-Find und Entwurfstechniken: Dynamic Programming, Greedy, Backtracking

Track Konzepte · Algorithmen · ca. 45 Min.

Worum es geht

Gehören diese zwei Konten zum selben Kunden? Warum braucht eine rekursive Funktion für n = 30 plötzlich Millionen Aufrufe? Und warum findet “immer das Beste zuerst nehmen” manchmal nicht die beste Lösung? Hier lernst du ein Werkzeug für die erste Frage (Union-Find, disjoint set union) und die Entwurfstechniken für die beiden anderen (Dynamic Programming, DP, und Greedy, gierig).

Was du aus Teil a brauchst: Du kennst Graphen als Adjazenzliste, BFS und Dijkstra und weißt, dass Zyklen in Graphen ein eigenes Thema sind. Teil a: Graphen: BFS, DFS, topologische Sortierung und Dijkstra. Die Schritte hier sind in sich geschlossen.

Am Ende von Teil b kannst du:

mit Union-Find Zusammengehörigkeit verwalten und erkennen, warum zwei kleine Tricks es fast konstant schnell machen (Übung 1),
mit Dynamic Programming aus einer exponentiellen Rekursion eine lineare machen (Übung 2),
die Greedy-Falle (greedy) erklären und bei einem Problem die passende Entwurfstechnik wählen (Übung 3).

Plane ehrlich 45 Minuten ein: etwa 20 Minuten Lesen, 21 Minuten Übungen (drei Stück).

Von JS/TS her gedacht

In JS/TS gibt es für beides keine Standardbausteine. Union-Find schreibst du selbst (zwei Arrays parent und size), und Memoization baust du mit einer Map oder einem Objekt als Cache. In Python liegt für den Cache etwas Fertiges bereit:

Baustein	JS/TS	Python
Union-Find	selbst gebaut mit zwei Arrays	selbst gebaut mit zwei Listen (hier unten)
Cache für DP (Memoization)	`Map` im Closure	`dict` im Closure oder `functools.lru_cache`
Tabelle von unten (Tabulation)	`new Array(n + 1).fill(0)`	`[0] * (n + 1)`

Die Entwurfstechniken selbst (Greedy, DP, Backtracking) sind sprachunabhängig. Nur die Schreibweise ändert sich.

Konzept

Schritt 1: Union-Find, wer gehört zusammen?

Gegeben sind viele Paare “A und B gehören zusammen” (Konten desselben Kunden, Rechner im selben Netz), und zu jedem Zeitpunkt fragst du “gehören X und Y zur selben Gruppe?”. Union-Find verwaltet Gruppen als Bäume: Jedes Element zeigt auf ein Eltern-Element, die Wurzel (root) zeigt auf sich selbst und ist der Name der Gruppe.

find(x): laufe zu den Eltern hoch, bis du die Wurzel erreichst.
union(a, b): finde beide Wurzeln und hänge eine unter die andere. Sind es schon dieselben, passiert nichts.

Zwei Tricks machen das schnell, ohne sie entarten Bäume zu langen Ketten:

Pfadkompression (path compression): find hängt die besuchten Elemente direkt unter die Wurzel. Spätere find-Aufrufe sind kurz.
Union by size: Beim Verbinden kommt der kleinere Baum unter den größeren.

Mit beiden kostet eine Operation praktisch konstant viel (genau: Inverse der Ackermann-Funktion, allgemeines Fachwissen). Ein Beispiel mit sechs Elementen:

Ausgabe:

[True, True, False, True]
[0, 0, 0, 2, 4, 5]
[0, 0, 0, 0, 4, 5]

Lies es: union(0, 1) und union(2, 3) verbinden neue Gruppen (True). union(1, 0) ist schon verbunden (False). union(1, 3) verbindet die beiden Gruppen: Die Wurzel 2 hängt jetzt unter 0. Das Element 3 zeigt noch auf 2 (zweite Zeile, eltern), das ist ein Umweg über zwei Stufen. Der Aufruf find(3) in der dritten Zeile läuft darüber und kürzt dabei (Pfad halbieren), danach zeigt 3 direkt auf 0. Es bleiben die Gruppen {0, 1, 2, 3}, {4}, {5}.

Einsatz: Zusammenhangskomponenten in einem Graphen zählen, Zyklen beim Kanten-Einfügen erkennen (union liefert False) und der Kruskal-Algorithmus für den minimalen Spannbaum (allgemeines Fachwissen, hier nicht gebaut).

Schritt 2: Entwurfstechniken, Dynamic Programming und die Greedy-Falle

Vier Techniken tauchen immer wieder auf:

Divide and Conquer (teile und herrsche): in kleinere gleichartige Probleme zerlegen, lösen, zusammensetzen. Binäre Suche und Merge Sort sind Beispiele (Lektion 20).
Greedy (gierig): immer den lokal besten Schritt nehmen und nie zurückgehen. Schnell, aber nur korrekt, wenn das Problem das hergibt. Dijkstra ist ein Greedy-Verfahren, das beweisbar stimmt.
Dynamic Programming: Löst die Rekursion dieselben Teilprobleme mehrfach, löse jedes einmal und merke das Ergebnis (memoization, oder Tabelle von unten nach oben). Es lohnt sich bei überlappenden Teilproblemen und wenn sich die Lösung aus Lösungen kleinerer Teile zusammensetzt.
Backtracking: Möglichkeiten Schritt für Schritt aufbauen, bei einer Sackgasse einen Schritt zurück. Sudoku-Löser und N-Damen sind typisch. Ohne gutes Abschneiden (Pruning) exponentiell.

Ein DP-Beispiel: Auf wie viele Arten kommst du eine Treppe mit n Stufen hoch, wenn du je 1 oder 2 Stufen nimmst? stufen(n) = stufen(n-1) + stufen(n-2). Wir zählen die Funktionsaufrufe:

Ausgabe:

20 naiv: (10946, 21891) mit Memo: (10946, 39)
30 naiv: (1346269, 2692537) mit Memo: (1346269, 59)

Dasselbe Ergebnis, aber bei n = 30 braucht die naive Rekursion 2,7 Millionen Aufrufe, die Memo-Variante 59. Naiv wächst die Zahl der Aufrufe exponentiell, denn bei n = 30 wird stufen(18) 233 Mal und stufen(10) sogar 10946 Mal neu gerechnet. Mit Memo gibt es nur n verschiedene Teilprobleme, jedes wird einmal gerechnet: linear.

Jetzt die Greedy-Falle. Du hast Münzen und willst einen Betrag mit möglichst wenigen Münzen zahlen. Greedy nimmt immer die größte passende Münze:

Ausgabe:

3 2
4 4

Bei den Münzen (1, 3, 4) und dem Betrag 6 nimmt Greedy 4 + 1 + 1 (drei Münzen), das Optimum ist 3 + 3 (zwei). Bei “normalen” Münzsystemen wie (1, 2, 5, 10) stimmt Greedy (hier: 4 und 4), deshalb fällt die Falle in Tests oft nicht auf. optimal ist die Tabellenform von DP: Für jeden Betrag b die beste Antwort aus den schon berechneten kleineren Beträgen. Merke: Greedy braucht einen Beweis, DP braucht überlappende Teilprobleme.

Dieselbe Tabellentechnik löst auch Auswahlprobleme wie das Rucksack-Problem (knapsack): Aus n Gegenständen mit Gewicht und Wert wählst du die Teilmenge mit dem größten Gesamtwert, die in die Kapazität passt. Die Tabelle hat eine Zeile pro Gegenstand und eine Spalte pro Restkapazität, und jede Zelle vergleicht “Gegenstand mitnehmen” mit “weglassen”. Gegenstände mal Kapazität Zellen, statt 2 hoch n Teilmengen.

Und kurz P vs. NP als Intuition (nur Text): Probleme in P lassen sich in polynomieller Zeit lösen (sortieren, kürzester Weg). Bei NP-schweren Problemen (z. B. Rundreise mit kürzester Gesamtstrecke, Travelling Salesman) kennt man keinen schnellen Algorithmus, nur das Prüfen einer vorgeschlagenen Lösung ist schnell. In der Praxis nimmt man dann Heuristiken (gute, aber nicht beweisbar beste Lösung) oder Approximationsalgorithmen (Lösung mit garantierter Abweichung vom Optimum). Wer in einer Anforderung ein solches Problem erkennt, sagt das früh, statt eine “perfekte” Lösung zu versprechen.

Falle

Union ohne Wurzeln. eltern[a] = b statt die Wurzeln zu verbinden, trennt Gruppen wieder auf, die schon verbunden waren (Übung 1).
Cache, der länger lebt als der Aufruf. Ein memo={} als Default-Argument (Python-Falle) wird zwischen Aufrufen mit anderen Parametern wiederverwendet und liefert falsche Werte (Übung 2).
Greedy ohne Beweis. Er sieht in den Standardfällen richtig aus und scheitert an einem ungünstigen Eingabesatz (Übungen 2 und 3).
DP ohne überlappende Teilprobleme. Wo jedes Teilproblem nur einmal vorkommt, bringt ein Memo nur Speicherverbrauch.

Übungen

Übung 1: Union-Find mit Pfadkompression (ca. 8 Min.)

Baue die Klasse UnionFind für die Elemente 0 bis n - 1:

find(x) liefert die Wurzel der Gruppe von x.
union(a, b) verbindet die Gruppen und liefert True, wenn sie vorher getrennt waren, sonst False.
anzahl() liefert die aktuelle Zahl der Gruppen.

Der Check prüft zwei Dinge. Erstens Richtigkeit gegen eine einfache, langsame Vergleichsimplementierung. Zweitens Tempo über das Verhalten: Er baut zwei lange Ketten (union(0, 1), union(1, 2) und so weiter, in der zweiten Kette mit vertauschten Argumenten, damit es nicht von deiner Hängerichtung abhängt) und ruft danach 600 Mal find auf. Er zählt dabei, wie viele Zeilen dein Code (Methoden und eigene Hilfsfunktionen) ausführt. Ohne Pfadkompression und Union by Size sind das weit über 100000, mit mindestens einem der beiden Tricks nur etwa 17000. Das Limit liegt bei 60000. Eine Zeitmessung wäre im Browser unzuverlässig, Schritte zählen nicht.

Die letzte Zeile gibt die Klasse zurück.

class UnionFind:
    def __init__(self, n):
        self.eltern = list(range(n))
        self.groesse = [1] * n
        self.gruppen = n

    def find(self, x):
        while self.eltern[x] != x:
            self.eltern[x] = self.eltern[self.eltern[x]]
            x = self.eltern[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.groesse[ra] < self.groesse[rb]:
            ra, rb = rb, ra
        self.eltern[rb] = ra
        self.groesse[ra] += self.groesse[rb]
        self.gruppen -= 1
        return True

    def anzahl(self):
        return self.gruppen

UnionFind

Jedes Element beginnt als eigene Wurzel. union verbindet die Wurzeln und zählt die Gruppen um eins herunter, wenn wirklich zwei getrennte zusammenkommen. Der kleinere Baum hängt unter dem größeren (Union by Size), und find halbiert den Pfad (Pfadkompression). Eines der beiden reicht für den Check, beide zusammen sind der Standard.

Übung 2: Dynamic Programming, aus exponentiell wird linear (ca. 8 Min.)

Eine Versandabteilung packt genau n Artikel in Kartons. Es gibt Kartongrößen (Anzahl Artikel), z. B. (1, 6, 10), jede Größe beliebig oft. Schreibe min_kartons(groessen, n): die kleinste Zahl Kartons, die zusammen genau n Artikel fassen, oder None, wenn es nicht aufgeht.

Beispiele: min_kartons((1, 6, 10), 12) ergibt 2 (6 + 6). min_kartons((4, 9), 0) ergibt 0. min_kartons((2,), 7) ergibt None.

Zwei Anforderungen im Check:

Richtig, auch bei Größen, bei denen “immer den größten Karton zuerst” daneben liegt.
Schnell: Bei n = 200 und den Größen (1, 7, 13, 29) zählt der Check alle Python-Funktionsaufrufe. Erlaubt sind höchstens 40 pro Artikel (8000). Eine naive Rekursion wächst für dieses n so stark, dass sie nie fertig würde (der Check bricht vorher ab). Memoization oder eine Tabelle von unten nach oben funktionieren beide.

Die letzte Zeile gibt die Funktion zurück.

def min_kartons(groessen, n):
    beste = [0] + [None] * n
    for menge in range(1, n + 1):
        kandidaten = [beste[menge - g] + 1 for g in groessen
                      if g <= menge and beste[menge - g] is not None]
        beste[menge] = min(kandidaten) if kandidaten else None
    return beste[n]

min_kartons

Tabelle von unten nach oben: beste[m] ist die beste Antwort für m Artikel, gebaut aus den schon bekannten kleineren Werten. Jede Zahl von 0 bis n wird einmal berechnet, es gibt keinen Mehrfach-Aufruf. None markiert Unmögliches und wird beim Kombinieren übersprungen. Dieselbe Idee als Rekursion mit functools.lru_cache oder einem lokalen memo-Dict ginge auch.

Übung 3: Die passende Entwurfstechnik wählen (ca. 5 Min.)

Ein Lieferdienst belädt einen Wagen. Es gibt 40 Aufträge, jeder hat ein ganzzahliges Gewicht in kg und einen Wert. Der Wagen trägt höchstens 50 kg. Gesucht ist die Auswahl mit dem größten Gesamtwert, und zwar exakt (keine Näherung). Die Berechnung soll in unter einer Sekunde fertig sein. Dein Kollege schlägt vor:

A: Die Aufträge nach Wert pro kg absteigend sortieren und der Reihe nach einladen, solange noch Platz im Wagen ist.
B: Die Aufträge in zwei Hälften teilen, jede Hälfte für sich mit 25 kg optimal laden und beides zusammenlegen.
C: Alle Teilmengen der 40 Aufträge durchprobieren und die wertvollste nehmen, die höchstens 50 kg wiegt.
D: Eine Tabelle über (Aufträge, Restgewicht) aufbauen und in jeder Zelle “mitnehmen” mit “weglassen” vergleichen.

Gib den Buchstaben als String zurück.

antwort = "D"
antwort

D ist Dynamic Programming: Die Tabelle hat 40 mal 50 = 2000 Zellen, jede wird einmal berechnet, und das Ergebnis ist exakt. A ist Greedy ohne Beweis und liefert hier nicht immer das Optimum. B teilt auch die Kapazität, aber ein guter Gesamtplan muss die 50 kg nicht gleichmäßig verteilen. C ist exakt, aber 2 hoch 40 sind etwa 1,1 Billionen Teilmengen.

Merksatz

Union-Find beantwortet “gehört das zusammen?” fast in konstanter Zeit, Dynamic Programming löst jedes Teilproblem nur einmal, und Greedy ist nur mit Beweis korrekt.

Prüfstein

Woran erkennst du, dass Dynamic Programming passt, und warum ist “immer das Beste zuerst nehmen” nicht automatisch richtig?

Quelle: quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “2. Datenstrukturen und Algorithmen” (Rekursion und Divide and Conquer, Dynamic Programming auf Ideenebene). quellen/konzeptuebersicht-software-fortgeschritten.docx, Abschnitt “2. Algorithmen und Datenstrukturen im Einsatz” (Union-Find; Entwurfstechniken: Dynamic Programming, Greedy, Backtracking; P vs. NP als Intuition, Heuristiken und Approximation).

Über die Quelle hinaus (allgemeines Fachwissen): die Aussage zur Inverse der Ackermann-Funktion bei Union-Find, der Kruskal-Algorithmus, die Definitionen von Memoization, überlappenden Teilproblemen und Backtracking, die Erläuterung von P, NP und Approximation (nur Text), das Rucksack-Problem in Übung 3. Alle Zahlen und Ausgaben in dieser Lektion stammen aus dem Ausführen des Codes mit Python 3.