Backtracking

Manche Aufgaben lassen sich nicht in einem Zug lösen. Man muss raten, weiterbauen und merkt erst später, dass es nicht aufgeht. Backtracking ist die Strategie, in genau diesem Moment zurückzugehen. Man nimmt die letzte Entscheidung zurück und probiert die nächste Alternative. Ein Sudoku löst man so: Ziffer eintragen, weiterrechnen, bei einem Widerspruch die Ziffer wieder ausradieren und die nächste testen. Der Name sagt es wörtlich, denn « to backtrack » heißt « seine Spur zurückverfolgen ».

Warum stures Durchprobieren nicht reicht

Bei vielen Aufgaben ist die Zahl der Möglichkeiten absurd groß. Ein klassisches Beispiel ist das Acht-Damen-Problem: Acht Schachdamen sollen so auf ein Brett gestellt werden, dass keine eine andere bedroht. Wer alle Stellungen einzeln aufschreibt, kommt auf Milliarden von Fällen. Ein Computer würde daran lange rechnen, obwohl die Lösung eigentlich einfach ist.

Backtracking spart deshalb Arbeit, indem es früh abbricht. Stehen zwei Damen bereits in derselben Reihe, ist jede weitere Ergänzung sinnlos. Der Algorithmus kehrt sofort um und ignoriert damit Millionen von Stellungen auf einen Schlag. Fachleute nennen das « Pruning », also Beschneiden, wie bei einem Baum, dem man ganze Zweige abschneidet.

Der Trick ist also nicht Geschwindigkeit, sondern das Vermeiden von unnötiger Arbeit. Trotzdem bleibt Backtracking im schlimmsten Fall langsam. Wenn kein Zwischenschritt vorzeitig als falsch erkennbar ist, wird doch alles durchprobiert. Deshalb hängt die Qualität eines Backtracking-Programms davor ab, wie gut es Fehlwege früh erkennt.

Vorwärts raten, rückwärts korrigieren

Ein Backtracking-Verfahren arbeitet in Schritten. Es trifft eine Teilentscheidung, prüft, ob diese noch mit den Regeln vereinbar ist, und geht dann tiefer. Ist alles gültig und die Aufgabe vollständig gelöst, ist man fertig. Ist die Teilentscheidung dagegen unhaltbar, wird sie zurückgenommen.

Man kann sich das als Irrgarten vorstellen. An jeder Gabelung wählt man einen Gang und merkt sich, welche Gänge man dort noch nicht getestet hat. Endet der Weg an einer Wand, läuft man zur letzten Gabelung zurück. So durchsucht man den ganzen Irrgarten, ohne einen Weg zweimal zu gehen. Programmierer setzen das meist mit Rekursion um, also mit einer Funktion, die sich selbst für den nächsten Schritt aufruft.

Wichtig ist die Abgrenzung zu einem verwandten Ansatz. Beim Backtracking gibt es feste Regeln, die eine Teillösung entweder erlauben oder verbieten. Bei Optimierungsverfahren geht es dagegen darum, eine Lösung nur schrittweise zu verbessern. Ein häufiger Irrtum ist außerdem, Backtracking für einen Notbehelf zu halten. Für Aufgaben mit harten Nebenbedingungen ist es oft das beste bekannte Verfahren.

Von Sudoku-Apps bis zu KI-Modellen

Im Alltag steckt Backtracking in Rätsel-Apps, in Stundenplan-Software und in Programmen für Dienstpläne. Auch die Suchfunktion für Textmuster in einem Editor nutzt es. Wenn ein Muster mehrere Deutungen zulässt, probiert die Software eine davon und geht bei Misserfolg zurück. Genau das macht solche Suchen in seltenen Fällen sehr langsam.

In KI-News fällt das Wort inzwischen in einem zweiten Zusammenhang. Sprachmodelle, also Programme wie ChatGPT, die Texte Wort für Wort erzeugen, können sich beim Lösen einer Aufgabe verrennen. Neuere Systeme sind darauf trainiert, einen begonnenen Gedankengang zu verwerfen und einen anderen Ansatz zu versuchen. Firmen beschreiben dieses Verhalten gern als Backtracking im Denkprozess.

Der Vergleich ist allerdings nur teilweise korrekt. Ein klassischer Algorithmus verwirft einen Zweig, weil eine Regel eindeutig verletzt ist. Ein Sprachmodell schätzt lediglich, dass ein anderer Weg wahrscheinlich besser passt. Für Leser von Tech-Meldungen lohnt es sich deshalb, beide Bedeutungen auseinanderzuhalten.