Backtracking (deutsch: Zurückverfolgen) ist ein Algorithmus-Paradigma für Such- und Entscheidungsprobleme. Es probiert Lösungen systematisch Schritt für Schritt aus und zieht sich bei einer Sackgasse zurück, um andere Wege zu erkunden. Backtracking ist eng mit der Rekursion verwandt und arbeitet wie eine Tiefensuche im Lösungsbaum.
Grundprinzip
Ein Backtracking-Algorithmus baut eine Kandidatenlösung schrittweise auf:
- Ist die Teillösung vollständig und gültig → Lösung gefunden (oder nächste suchen).
- Ist die Teillösung ungültig oder kann sie nicht mehr gültig werden → Backtrack: letzten Schritt rückgängig machen, nächste Alternative probieren.
- Sonst → nächsten Kandidaten hinzufügen und rekursiv weiterprüfen.
Durch das frühzeitige Verwerfen aussichtsloser Teilpfade (Pruning) wird viel weniger durchsucht als beim naiven Ausprobieren aller Kombinationen.
Klassische Beispiele
- N-Damen-Problem: N Damen so auf ein Schachbrett stellen, dass keine sich bedroht.
- Sudoku: Felder systematisch füllen und bei Widersprüchen zurücksetzen.
- Rucksack-Problem (0/1): Kombinationen von Gegenständen testen, Gewichtsgrenze beachten.
- Graph-Färbung, Labyrinth-Suche, Hamilton-Pfade (u.a. für Graphtraversierung und Routenplanung).
Backtracking im Vergleich
Dynamische Programmierung ist Backtracking mit Gedächtnis: Sie speichert Lösungen bereits gelöster Teilprobleme und vermeidet so doppelte Berechnungen. Greedy-Algorithmen entscheiden dagegen nur einmal lokal und nehmen Entscheidungen nie zurück. Backtracking garantiert die vollständige Suche, zahlt aber im schlechtesten Fall exponentielle Laufzeit — die Big-O-Notation macht das sichtbar. Bei kombinatorischen Problemen auf Graphen ist Backtracking oft die einzige praktikable exakte Methode.
Verwandte Grundlagen: Rekursion, Dynamische Programmierung, Divide and Conquer, Traversierung.