Backtracking
Was ist Backtracking?
Backtracking ist ein algorithmisches Suchverfahren, das mögliche Lösungen schrittweise aufbaut und eine Entscheidung zurücknimmt, sobald der eingeschlagene Weg keine gültige Lösung mehr liefern kann. Die Methode wird bei kombinatorischen Aufgaben, Planung, Rätseln und regulären Ausdrücken eingesetzt. Durch frühes Verwerfen ungeeigneter Wege lässt sich der Suchraum häufig deutlich verkleinern.
Wie funktioniert Backtracking?
Backtracking durchsucht einen Entscheidungsbaum meist in der Tiefe. Das Verfahren wählt eine mögliche Option, ergänzt damit die bisherige Teillösung und prüft unmittelbar, ob alle Bedingungen weiterhin erfüllt sind. Ist eine Bedingung verletzt, kehrt der Algorithmus zum letzten Entscheidungspunkt zurück. Diese Rücksetzsuche, deutsch für Backtracking, wird fortgesetzt, bis eine Lösung gefunden oder der gesamte relevante Suchraum geprüft wurde.
Ein Backtracking-Algorithmus besteht typischerweise aus vier Schritten:
Die wichtigste Eigenschaft von Backtracking ist das frühe Verwerfen ungeeigneter Teilbäume. Ein Algorithmus muss einen Weg nicht vollständig verfolgen, wenn bereits feststeht, dass daraus keine gültige Gesamtlösung entstehen kann. Die Qualität der Prüfregeln bestimmt deshalb maßgeblich, wie viele Zustände tatsächlich untersucht werden.
Backtracking als Suchbaum
Ein Suchbaum bildet jede Entscheidung als Knoten und jede mögliche Auswahl als Kante ab. Hat eine Aufgabe pro Ebene höchstens b Kandidaten und eine maximale Entscheidungstiefe von d, kann ein vollständiges Durchsuchen im ungünstigsten Fall eine Größenordnung von O(bd) erreichen. Backtracking garantiert daher nicht automatisch eine kurze Laufzeit.
Die Speicheranforderung fällt bei einer tiefenorientierten Umsetzung häufig geringer aus als der Zeitaufwand. Speichert der Algorithmus nur den aktuellen Pfad, liegt der zusätzliche Speicherbedarf typischerweise in der Größenordnung O(d). Werden alle gefundenen Lösungen gesammelt, kommt der Speicherbedarf für diese Ergebnisse hinzu.
Abbruchbedingungen festlegen
Eine saubere Abbruchbedingung verhindert unnötige Suchschritte. Backtracking endet je nach Aufgabe, wenn die erste gültige Lösung gefunden wurde, alle Lösungen aufgelistet sind oder kein zulässiger Kandidat mehr existiert. Vor der Implementierung solltest du deshalb festlegen, ob eine beliebige Lösung, die optimale Lösung oder die vollständige Lösungsmenge gesucht wird.
Kandidaten gezielt anordnen
Die Reihenfolge der Kandidaten verändert die Korrektheit eines vollständigen Backtracking-Verfahrens nicht, kann die Laufzeit bis zur ersten Lösung aber stark beeinflussen. Vielversprechende oder besonders stark einschränkende Optionen sollten früh geprüft werden. Diese Heuristik senkt nicht zwingend die theoretische Worst-Case-Laufzeit, reduziert bei vielen Aufgaben jedoch die Zahl der tatsächlich besuchten Knoten.
Backtracking im Beispiel
Ein einfaches Schema für Backtracking lässt sich unabhängig von der Programmiersprache darstellen:
suche(teillösung):
wenn teillösung vollständig ist: Lösung ausgeben
sonst für jeden zulässigen Kandidaten:
Kandidaten hinzufügen
suche(teillösung)
Kandidaten entfernen
Das Entfernen des Kandidaten ist der eigentliche Rücksprung. Ohne diesen Schritt bliebe die vorherige Entscheidung in der Datenstruktur erhalten und würde alle weiteren Versuche verfälschen. Bei veränderlichen Listen, Mengen oder Spielbrettern muss Backtracking den Zustand deshalb vollständig wiederherstellen.
Messbar ist Backtracking zum Beispiel so: Protokolliere die Zahl der besuchten Zustände, verworfenen Teillösungen, rekursiven Aufrufe und gefundenen Lösungen. Eine Optimierung ist belastbar, wenn sie bei derselben Eingabe weniger Zustände untersucht oder weniger Laufzeit benötigt. Nur die Rekursionstiefe zu messen reicht nicht, weil zwei Verfahren bei identischer Tiefe unterschiedlich viele Verzweigungen prüfen können.
Unterschiede zu anderen Verfahren
Der Unterschied zwischen Backtracking und Brute Force liegt im Zeitpunkt des Verwerfens. Brute Force erzeugt oder prüft grundsätzlich alle vorgesehenen Kombinationen. Backtracking beendet einen Teilpfad bereits dann, wenn eine Bedingung verletzt ist. Fehlen solche Prüfregeln, verhält sich Backtracking faktisch wie eine tiefenorientierte vollständige Suche.
| Verfahren | Auswahlprinzip | Rücknahme von Entscheidungen | Typischer Zweck |
|---|---|---|---|
| Backtracking | Schrittweise Suche mit Zulässigkeitsprüfung | Ja | Eine oder alle gültigen Lösungen finden |
| Brute Force | Alle vorgesehenen Kombinationen prüfen | Nicht zwingend | Vollständige Suche ohne wirksame Einschränkung |
| Greedy-Verfahren | Lokal günstigste Auswahl treffen | Üblicherweise nein | Schnell eine geeignete Lösung konstruieren |
| Dynamische Programmierung | Teilergebnisse speichern und wiederverwenden | Nein | Wiederholte Teilprobleme effizient lösen |
| Branch and Bound | Teilbäume über Schranken ausschließen | Ja | Eine optimale Lösung nachweisen |
Backtracking sucht primär nach zulässigen Lösungen. Branch and Bound verwendet zusätzlich eine Zielfunktion und Schranken, um Teilbäume auszuschließen, die keine bessere Lösung als die bereits bekannte liefern können. Dynamische Programmierung eignet sich dagegen besonders, wenn identische Teilprobleme mehrfach auftreten und ihre Ergebnisse gespeichert werden können.
Backtracking bei regulären Ausdrücken
Einige Engines für reguläre Ausdrücke verwenden ebenfalls Backtracking. Kann ein Ausdruck auf mehrere Arten auf denselben Text passen, probiert die Engine zunächst einen Pfad und kehrt bei einem späteren Fehlschlag zu einer früheren Verzweigung zurück. Verschachtelte Wiederholungen und mehrdeutige Alternativen können dadurch sehr viele mögliche Zerlegungen erzeugen.
(a+)+$ können bei bestimmten Backtracking-Engines problematisch werden, wenn nach einer langen Folge von a-Zeichen noch ein unpassendes Zeichen folgt. Die Engine prüft dann zahlreiche Aufteilungen derselben Zeichenfolge. Begrenze Wiederholungen, vermeide unnötige Verschachtelungen und teste reguläre Ausdrücke mit langen, bewusst nicht passenden Eingaben. Relevanz für SEO, SEA und GEO
Backtracking ist weder ein Ranking-Faktor noch eine eigenständige Methode für SEO, SEA oder GEO, also Generative Engine Optimization. Der Begriff wird für Marketing-Verantwortliche relevant, wenn technische Systeme komplexe Regeln auswerten. Beispiele sind URL-Routing, Weiterleitungslogik, Datenvalidierung, Konfiguratoren und reguläre Ausdrücke zur Auswertung von Crawling- oder Logdaten.
Fehlerhafte oder unnötig komplexe Suchregeln können technische Prozesse verlangsamen. Bei einem Website-Relaunch betrifft das etwa umfangreiche Muster für Weiterleitungen. Eine SEO-Checkliste für den Website-Relaunch sollte deshalb auch Tests für Redirect-Regeln, Statuscodes und Ziel-URLs enthalten. Eine strukturierte technische SEO-Analyse deckt zusätzlich Weiterleitungsketten, unerreichbare Seiten und widersprüchliche Regeln auf.
Bei technischen Prüfungen zählt das Ergebnis mehr als die Bezeichnung des eingesetzten Algorithmus. Prüfe, ob Regeln terminieren, ob alle Eingaben einen definierten Zustand erzeugen und ob dieselben URLs reproduzierbar dasselbe Ergebnis liefern. Für umfangreiche Websites unterstützt ein SEO-Technik-Crawler die Kontrolle von Statuscodes, internen Links und technischen Fehlern.
Häufige Fragen zu Backtracking
Ist Backtracking immer rekursiv?
Nein. Backtracking wird häufig rekursiv programmiert, weil die Aufrufstruktur dem Suchbaum entspricht. Eine iterative Umsetzung ist ebenfalls möglich, wenn ein eigener Stapelspeicher die offenen Entscheidungen und Zustände verwaltet.
Findet Backtracking immer eine Lösung?
Backtracking findet eine Lösung, wenn eine existiert, der Suchraum endlich ist und das Verfahren alle zulässigen Möglichkeiten vollständig untersucht. Wird die Suche durch Zeitlimits, unvollständige Regeln oder Heuristiken vorzeitig beendet, entfällt diese Vollständigkeitsgarantie.
Kann Backtracking alle Lösungen ausgeben?
Ja. Nach einem Treffer darf der Algorithmus dafür nicht endgültig abbrechen. Backtracking speichert oder verarbeitet die gefundene Lösung, nimmt die letzte Entscheidung zurück und setzt die Suche mit den verbleibenden Kandidaten fort.
Wann ist Backtracking zu langsam?
Backtracking wird langsam, wenn der Suchbaum breit und tief ist und nur wenige Teilpfade früh ausgeschlossen werden können. Verbesserungen entstehen durch stärkere Zulässigkeitsprüfungen, eine geeignete Kandidatenreihenfolge, Symmetrieausschluss oder das Speichern wiederkehrender Teilprobleme.
Was bedeutet Backtracking bei Regex?
Bei regulären Ausdrücken bedeutet Backtracking, dass eine Engine zu einer früheren Verzweigung zurückkehrt und eine andere Zeichenaufteilung ausprobiert. Mehrdeutige, verschachtelte Wiederholungen können die Zahl dieser Versuche stark erhöhen.
Für welche Aufgaben eignet sich Backtracking?
Backtracking eignet sich für Aufgaben mit klaren Bedingungen und mehreren kombinierbaren Entscheidungen. Typische Beispiele sind Sudoku, Damenprobleme, Wegsuche, Stundenplanung, Zuordnungsprobleme und die Erzeugung gültiger Konfigurationen.
Wenn komplexe Regeln, Weiterleitungen oder technische Abhängigkeiten deine Website betreffen, schafft ein systematischer Potenzialcheck Klarheit über die nächsten Prüfschritte.
Kostenlosen Potenzialcheck anfragen
Sie haben noch Fragen?
