Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Du bist in einem Labyrinth und triffst eine Sackgasse. Was machst du? Du gehst zurück und probierst eine andere Abzweigung. Genau das ist Backtracking: systematisches Durchprobieren mit Rückzug bei Sackgassen. Klausur-Klassiker für NP-schwere Probleme wie 8-Damen, Sudoku, TSP. 8/17 WInf-Algo-Klausuren.
Klausur-Tipp: Bei Backtracking-Aufgaben zeichne den Such-Baum: jeder Knoten = Teil-Lösung, Kanten = Erweiterungen. Markiere Pruning-Stellen — das zeigt, warum Backtracking effizient bleibt trotz exponentiellem Worst Case.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Du bist in einem Labyrinth und triffst eine Sackgasse. Was machst du? Du gehst zurück und probierst eine andere Abzweigung. Genau das ist Backtracking: systematisches Durchprobieren mit Rückzug bei Sackgassen. Klausur-Klassiker für NP-schwere Probleme wie 8-Damen, Sudoku, TSP. 8/17 WInf-Algo-Klausuren.
Backtracking: Erweitere eine Teil-Lösung schrittweise. Wenn der aktuelle Pfad zu keiner gültigen Lösung führen kann (Sackgasse), gehe einen Schritt zurück und probiere eine Alternative.
Stelle dir alle möglichen Lösungs-Kandidaten als Baum vor:
Backtracking führt eine Tiefensuche (DFS) über diesen Baum durch, mit Pruning: schneide unmögliche Pfade früh ab.
Problem: Platziere 8 Damen auf einem 8×8-Schachbrett, sodass keine eine andere bedroht (keine in gleicher Zeile, Spalte oder Diagonale).
Backtracking-Lösung:
solve(board, col):
if col == 8: return True # alle Damen platziert
for row in 0..7:
if isSafe(board, row, col):
board[row][col] = "Q" # versuche Position
if solve(board, col + 1):
return True
board[row][col] = "." # backtrack: entferne Versuch
return False
Pro Spalte: versuche alle 8 Zeilen. Wenn keine funktioniert → rückwärts. Mit Pruning sind nur wenige Tausend statt 8⁸ = 16 Millionen Versuche nötig.
backtrack(partial_solution):
if is_complete(partial_solution):
record_solution(partial_solution)
return
for candidate in next_candidates(partial_solution):
if is_promising(candidate, partial_solution):
extend(partial_solution, candidate)
backtrack(partial_solution)
undo(partial_solution, candidate) # backtrack!
Ohne Pruning ist Backtracking = brute-force-Tiefensuche (O(b^d)).
Mit Pruning sind nur wenige Pfade tatsächlich besucht. Pruning-Strategien:
Backtracking pro leere Zelle: probiere 1-9, prüfe Sudoku-Regeln, weiter zur nächsten Zelle.
Für jedes Item: nimm oder nimm nicht. Backtracking über alle 2ⁿ Kombinationen — mit Pruning bei Kapazitäts-Überschreitung viel weniger.
Permutationen aller Städte. Pruning: wenn aktuelle Teil-Tour bereits länger als beste komplette Tour → abbrechen.
Färbe Knoten mit minimaler Farben-Anzahl, so dass keine 2 adjazenten gleich sind.
Verallgemeinerung von 8-Damen für beliebiges n.
Wähle Teilmenge der Eingabe-Zahlen, die exakt zu einer Ziel-Summe addieren.
| Paradigma | Eigenschaften |
|---|---|
| Greedy | Lokal beste Wahl, nie zurück, schnell, nicht immer optimal |
| DP | Speichert überlappende Teil-Lösungen, optimal, polynomial |
| Backtracking | Systematisches Durchprobieren mit Rückzug, optimal, oft exponentiell |
| D&C | Teile + löse Teile + kombiniere, polynomial bei unabhängigen Teilen |
Wann Backtracking? Wenn es viele Lösungs-Kandidaten gibt und keine bessere Strategie (DP, Greedy) funktioniert — typisch bei NP-schweren Problemen.
Worst Case: O(b^d) mit b = Branching-Faktor, d = Tiefe.
Average Case: durch Pruning deutlich besser. Schwer allgemein zu beschreiben — hängt vom Problem ab.
Beispiel 8-Damen: 8⁸ = 16M ohne Pruning, ~15k mit guten Constraints.
Für Optimierungs-Probleme: erweitere Backtracking um eine Schranke für den noch erreichbaren best/schlechtesten Wert.
branch_and_bound:
best_so_far = infinity
for each candidate:
if upper_bound(candidate) < best_so_far:
skip # diese Teil-Lösung kann nicht besser sein
else:
extend and recurse
Anwendung: optimale TSP-Lösung, optimaler Knapsack mit garantierter Optimalität.
1. Backtracking = systematische Tiefensuche mit Rückzug.
2. Pruning ist essentiell. Ohne Pruning oft exponentiell und unbenutzbar.
3. Pseudocode-Schema: if complete → record; for each candidate → extend + recurse + undo.
4. Klassiker: 8-Damen, Sudoku, N-Queens, Knapsack, TSP, Graph-Färbung.
5. Branch-and-Bound: Backtracking + Schranke für Optimierungs-Probleme.
1. undo vergessen. Beim Rückzug MUSS die Teil-Lösung wieder in den vorherigen Zustand gebracht werden. Sonst falsche Ergebnisse.
2. Constraint-Check zu spät. Wenn du erst am Ende prüfst, ob die Lösung gültig ist, hast du gar nicht backtracking — sondern brute force.
3. Backtracking als immer optimal annehmen. Korrektheit ist garantiert (findet ALLE Lösungen oder die beste), aber Laufzeit kann exponentiell sein.
4. Pruning vergessen. Ohne Pruning oft unbenutzbar in der Praxis. Constraints früh propagieren.
5. Backtracking mit Greedy verwechseln. Greedy macht eine Wahl und vergisst Alternativen. Backtracking probiert systematisch ALLE.
Sieh das 4-Damen-Problem mit Backtracking gelöst. Pro Schritt:
So entwickelst du Intuition für "systematisch durchprobieren mit Rückzug".
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei Backtracking-Aufgaben zeichne den Such-Baum: jeder Knoten = Teil-Lösung, Kanten = Erweiterungen. Markiere Pruning-Stellen — das zeigt, warum Backtracking effizient bleibt trotz exponentiellem Worst Case.
6 Aufgaben zu Backtracking-Prinzip, Pruning, klassischen Problemen.
Klausurfragen mit Lösungen (6)
Antwort: Systematisches Durchprobieren mit Rückzug bei Sackgassen
Erklärung: Backtracking: Tiefensuche durch alle Kandidaten, mit Rückzug bei Sackgassen (Constraints verletzt). Schließt unmögliche Pfade früh aus (Pruning) um exponentielle Laufzeit zu reduzieren.
Antwort: Binäre Suche
Erklärung: Binäre Suche ist Divide-and-Conquer, KEIN Backtracking. Es teilt das Suchintervall und geht in eine Richtung — kein Rückzug nötig. 8-Damen, Sudoku, 0/1-Knapsack sind Backtracking-Klassiker.
Antwort: Wahr
Erklärung: RICHTIG. Ohne Constraint-Check + früher Abbruch ist Backtracking = einfacher rekursiver Such-Baum-Durchlauf. Mit b Verzweigungen pro Knoten und Tiefe d: O(b^d). Pruning macht den Unterschied praktisch und theoretisch.
Typ: Wahr/Falsch
Antwort: Unmögliche Pfade früh abschneiden, bevor sie komplett exploriert werden
Erklärung: Pruning: bei Constraint-Verletzung sofort den ganzen Teilbaum verwerfen statt blind weiterzusuchen. Beispiel: 8-Damen, wenn 2 Damen in gleicher Diagonale → keine weitere Spalte versuchen, direkt zurück.
Richtige Antworten: Backtracking findet alle Lösungen, wenn man weiter sucht; Branch-and-Bound ist Backtracking + Schranke für Optimierung; 8-Damen kann mit Backtracking effizient gelöst werden; Backtracking hat im Worst Case exponentielle Laufzeit
Erklärung: Richtig: findet alle Lösungen, Branch-and-Bound, 8-Damen, exponentieller Worst Case. Falsch: Backtracking funktioniert AUCH bei NP-schweren Problemen (nur halt exponentiell); DP ist oft schneller bei überlappenden Teilproblemen.
Typ: Multi-Select
Zuordnungen:
Erklärung: Vier algorithmische Paradigmen. Jedes mit eigener Stärke. Backtracking ist die 'Try-everything-Methode' mit Smart-Pruning.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
Antwort: for candidate in next_candidates: extend, recurse, undo
Erklärung: Standard-Schleife: für jeden Kandidaten: erweitere Teil-Lösung, rekursiv weiter, undo (zurücksetzen für nächsten Kandidaten). Das undo ist DER Backtracking-Schritt.
Antwort: Wahr
Erklärung: RICHTIG. Branch-and-Bound = Backtracking + zusätzliche Pruning-Regel: Berechne Upper Bound für jeden Pfad. Wenn UB < bisheriges Bestes → Pfad nicht weiter verfolgen. Sehr effektiv bei TSP, Knapsack.
Typ: Wahr/Falsch
Antwort: 8⁸ ≈ 16 Mio
Erklärung: Naiv: für jede der 8 Spalten 8 mögliche Zeilen → 8⁸ = 16.777.216 Versuche. Mit Backtracking + Pruning: nur ca. 15.000 tatsächlich besuchte Pfade. Pruning macht's praktisch.
Antwort: Quicksort (Standard-Implementation)
Erklärung: Quicksort ist DIVIDE-AND-CONQUER, kein Backtracking. Es teilt um ein Pivot, sortiert rekursiv beide Hälften — kein Rückzug. 8-Damen, Sudoku, TSP-B&B sind Backtracking/Branch-and-Bound.
Lösungen pro Lücke:
Erklärung: Backtracking-Vokabular. Tiefensuche, Pruning, Branch-and-Bound, 8-Damen, exponentielle Worst-Case-Laufzeit.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-Backtracking-Schleife. Check → Kandidat → Constraint-Test → Erweitern → Rekursion → Undo. Letzteres ist der namensgebende Schritt.
Typ: Reihenfolge