WikiDer > Zurückverfolgung
zurückverfolgen ist eine Methode für Suchprobleme im in Informatik. Backtracking ist bequemer als das rohe Gewalt Methode, da nicht alle Lösungen berücksichtigt werden müssen. Der Begriff wurde erstmals um 1950 von den MathematikerDerrick Henry Lehmer.
Bei Suchproblemen muss aus einer Reihe plausibler Möglichkeiten eine Lösung ausgewählt werden. Bei der Lösung des Problems müssen Entscheidungen getroffen werden. Wenn sich im Nachhinein herausstellt, dass eine getroffene Wahl nicht zu einer Lösung oder nicht zu einer optimalen Lösung führt, muss man zum Moment der Wahl zurückkehren. Diese Rückkehr heißt zurückverfolgen. Auch die Lösungsmethode als Ganzes (die Algorithmus) nennt man Backtracking: Nach einer neuen Wahl läuft der Algorithmus weiter, bis er wieder zurückkehren muss oder eine gute Lösung findet.
Anwendungen
Backtracking wird hauptsächlich bei der Bewertung verwendet Reguläre Ausdrücke. Besonders Programmiersprachen, wie Prolog, verlassen sich ganz auf dieses Prinzip.
Ein weiterer Algorithmus, der Backtracking verwendet, ist der DPLL-Algorithmus, für die erfüllen einer logischen Formel, die auf die Wahl der wörtlich die auserwählt wurde zu erfüllen.
Siehe auch
Literatur
- Gilles Brassard, Paul Bratley, Grundlagen der Algorithmik. Lehrlingssaal (1995).