Backtracking (Rücksetzverfahren)
Die Kurzantwort · 17 Wörter
Kurz erklärt
Algorithmische Suchtechnik, die eine Teilentscheidung zurücknimmt, sobald erkennbar ist, dass sie nicht zu einer gültigen Lösung führt.
Flow-alerta.cab (2026): Backtracking (Rücksetzverfahren). https://flow-alerta.cab/glossar/backtracking. Redaktionell geprüft am: 09. Oktober 2026.
Wie ausführlich soll es sein?
Praxis
Grundtechnik für kombinatorische Probleme wie Zuordnung, Konfiguration, Rätsel, Constraint-Satisfaction und bestimmte Planungsaufgaben.
Beispielszenario: Bei einer Einsatzplanung wird eine unzulässige Zuordnung verworfen und die vorherige Entscheidung mit einer anderen Ressource erneut versucht.
Sinnvoll für kleine oder gut beschränkte Konfigurationsprobleme; bei großen Suchräumen zusätzliche Heuristiken, Constraints oder andere Optimierungsverfahren prüfen.
Auf einen Blick
- Kern
- Backtracking baut eine Lösung schrittweise auf. Führt eine Wahl in eine Sackgasse, springt das Verfahren zum letzten Entscheidungspunkt zurück und probiert eine Alternative. Konzeptionell entspricht das häufig einer Tiefensuche im Baum möglicher Teillösungen.
- Nutzen
- Grundtechnik für kombinatorische Probleme wie Zuordnung, Konfiguration, Rätsel, Constraint-Satisfaction und bestimmte Planungsaufgaben.
- Beispiel
- Beispielszenario: Bei einer Einsatzplanung wird eine unzulässige Zuordnung verworfen und die vorherige Entscheidung mit einer anderen Ressource erneut versucht.
- Grenzen
- Backtracking mit dynamischer Programmierung verwechseln; keine frühen Ausschlussbedingungen nutzen; exponentielle Laufzeit unterschätzen; alle Suchprobleme als effizient lösbar darstellen.
Fragen, die dazu gestellt werden
Findet Backtracking immer schnell eine Lösung? Nein. Ist es dasselbe wie Brute Force? Es durchsucht ebenfalls Möglichkeiten, kann aber unbrauchbare Teilzweige früh verwerfen. Kann es rekursiv umgesetzt werden? Häufig ja.
Alle Details und Hintergründe
Backtracking baut eine Lösung schrittweise auf. Führt eine Wahl in eine Sackgasse, springt das Verfahren zum letzten Entscheidungspunkt zurück und probiert eine Alternative. Konzeptionell entspricht das häufig einer Tiefensuche im Baum möglicher Teillösungen.
ELI5 – Einfach erklärt
Du probierst einen Weg. Wenn er nicht funktioniert, gehst Du zum letzten Abzweig zurück und nimmst den nächsten Weg.
Warum das im Alltag wichtig ist
Grundtechnik für kombinatorische Probleme wie Zuordnung, Konfiguration, Rätsel, Constraint-Satisfaction und bestimmte Planungsaufgaben.
Beispiel
Beispielszenario: Bei einer Einsatzplanung wird eine unzulässige Zuordnung verworfen und die vorherige Entscheidung mit einer anderen Ressource erneut versucht.
Fallstricke und Grenzen
- Backtracking mit dynamischer Programmierung verwechseln; keine frühen Ausschlussbedingungen nutzen; exponentielle Laufzeit unterschätzen; alle Suchprobleme als effizient lösbar darstellen.
Entstehung & Geschichte
Backtracking wurde als allgemeine Programmiertechnik bereits früh in der Informatik beschrieben. Eine bekannte frühe Darstellung stammt von Golomb und Baumert aus dem Jahr 1965.
Anwendung im Mittelstand
- Sinnvoll für kleine oder gut beschränkte Konfigurationsprobleme; bei großen Suchräumen zusätzliche Heuristiken, Constraints oder andere Optimierungsverfahren prüfen.
Verwandte Begriffe
- Tiefensuche
- Rekursion
Passende Flow-alerta-Leistung
Websites & Web-AnwendungenWebsites & Web-Anwendungen: technische Umsetzung und Prüfung einer passenden Webanwendung.Passendes Tool / Use Case
Praxisbeispiele ansehenUse Case: regelkonforme Kombination von Optionen in einem Konfigurator.Quellen
- xlinux.nist.govNIST Dictionary of Algorithms and Data Structures, Backtracking
Quellenprüfung: 09.10.2026. Definition und dokumentierte Einordnung abgeglichen; Beispiele beschreiben mögliche Anwendungen.
Redaktionell geprüft am: