Backtracking.

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.

Die Idee in einem Satz

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.

Backtracking als Such-Baum

Stelle dir alle möglichen Lösungs-Kandidaten als Baum vor:

• Wurzel: leere Teil-Lösung
• Kanten: "fügt nächstes Element hinzu"
• Blätter: komplette Lösungen (gültig oder nicht)

Backtracking führt eine Tiefensuche (DFS) über diesen Baum durch, mit Pruning: schneide unmögliche Pfade früh ab.

Klassisches Beispiel: 8-Damen-Problem

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.

Pseudocode-Schema

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!

Pruning: das Geheimnis

Ohne Pruning ist Backtracking = brute-force-Tiefensuche (O(b^d)).

Mit Pruning sind nur wenige Pfade tatsächlich besucht. Pruning-Strategien:

1. Constraint Propagation: Schließe Zellen aus, die andere Damen-Positionen blockieren
2. Branch-and-Bound: Bei Optimierungs-Problemen: schneide Pfade ab, deren bestmögliche Lösung schlechter als bestes gefundenes Optimum ist
3. Ordering Heuristics: Probiere "vielversprechendere" Kandidaten zuerst

Weitere klassische Probleme

Sudoku

Backtracking pro leere Zelle: probiere 1-9, prüfe Sudoku-Regeln, weiter zur nächsten Zelle.

Knapsack (0/1)

Für jedes Item: nimm oder nimm nicht. Backtracking über alle 2ⁿ Kombinationen, mit Pruning bei Kapazitäts-Überschreitung viel weniger.

Traveling Salesman (TSP)

Permutationen aller Städte. Pruning: wenn aktuelle Teil-Tour bereits länger als beste komplette Tour → abbrechen.

Graph-Färbung

Färbe Knoten mit minimaler Farben-Anzahl, so dass keine 2 adjazenten gleich sind.

N-Queens

Verallgemeinerung von 8-Damen für beliebiges n.

Subset Sum

Wähle Teilmenge der Eingabe-Zahlen, die exakt zu einer Ziel-Summe addieren.

Backtracking vs. DP vs. Greedy

Wann Backtracking? Wenn es viele Lösungs-Kandidaten gibt und keine bessere Strategie (DP, Greedy) funktioniert, typisch bei NP-schweren Problemen.

Komplexität

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.

Branch-and-Bound (Spezialform)

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.

Klausur-Faustregeln

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.

Häufige Stolpersteine

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.

4-Damen-Backtracking-Stepper

Sieh das 4-Damen-Problem mit Backtracking gelöst. Pro Schritt:

• Aktuelle Brett-Position
• Versuchte Damen-Position (gelb)
• Konflikte (rot markiert)
• Backtrack-Schritte wenn keine Lösung in Sicht

So entwickelst du Intuition für "systematisch durchprobieren mit Rückzug".

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.

Backtracking, Praxis-Übung

6 Aufgaben zu Backtracking-Prinzip, Pruning, klassischen Problemen.