Backtracking
Backtracking explored systematisch alle Kandidatenlösungen und macht Auswahlentscheidungen rückgängig (verfolgt zurück), wenn ein Zweig unzulässig wird; es wird für Constraint-Satisfaction-Probleme eingesetzt.
Zweck
Kombinatorische Such- und Constraint-Satisfaction-Probleme wie das N-Damen-Problem oder Sudoku lösen.
Mechanismus
Es durchsucht den Baum des Lösungsraums tiefensucherisch, erweitert in jedem Schritt einen Kandidaten und verfolgt bei Einschränkungsverletzung zurück. Pruning (Constraint-Propagation, Schranken) verkleinert den Suchraum. Klassiker: N-Damen, Graphfärbung, Subset Sum.
Anwendungsfälle
- Constraint-Erfüllung
- Kombinatorische Suche
- Puzzle-Lösung