Backtracking: Versuch und Rücknahme

Backtracking erkundet einen Entscheidungsbaum: treffe eine Wahl, gehe rekursiv weiter, nimm die Wahl zurück (undo), probiere die nächste Alternative.

Es ist Trial and Error mit systematischem Rückzug. Ohne Undo bleiben falsche Teilzustände stehen.

Entscheidungen zurücknehmen: Permutations [1].

Wo gebraucht

Constraint Solver, Sudoku/Planung, Feature-Toggle-Kombinationen, Regex-Engines (mit Cuts), Spielesuche. Versuch und Undo ist das Kontrollmuster hinter vielen NP-schwierigen Exact-Solvern.

Vertiefung

Backtracking durchsucht einen Baum von Teilentscheidungen. Jeder Knoten beschreibt einen teilweise konstruierten Kandidaten, jede Kante ergänzt eine Wahl. Nach einem erfolglosen Zweig wird der vorherige Zustand wiederhergestellt, damit der nächste Zweig unter denselben Ausgangsbedingungen beginnt.

Die zentrale Invariante lautet: Beim Eintritt in eine Rekursionsebene enthält der Zustand genau die Entscheidungen des aktuellen Pfades. Zulässigkeitstests können Zweige früh verwerfen. Ihre Qualität entscheidet oft stärker über die Laufzeit als die eigentliche Rekursion, obwohl die Zahl möglicher Pfade im ungünstigen Fall exponentiell bleibt.

Schwierigkeitsstufen

1. Einen vollständigen Entscheidungsbaum für wenige Wahlmöglichkeiten zeichnen.
2. Einen Zulässigkeitstest formulieren, der keine gültige Lösung verwirft.
3. Suchreihenfolge und Schranken so wählen, dass grosse Teilbäume früh entfallen.

Fallstricke

Häufig werden Änderungen nicht vollständig rückgängig gemacht oder globale Daten zwischen Geschwisterzweigen geteilt. Ein zu aggressiver Schnitt ist ebenfalls falsch: Er verbessert scheinbar die Laufzeit, kann aber Lösungen unbemerkt entfernen.