Backtracking

Backtracking is a type of algorithm that is a refinement of brute force search. [cite web | url=http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128 Backtracking algorithms | title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms | year=1999 | author=Gurari, Eitan] In backtracking, multiple solutions can be eliminated without being explicitly examined, by using specific properties of the problem. It can be a strategy for finding solutions to constraint satisfaction problems. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s.

Explanation

Constraint satisfaction problems are problems with a complete solution, where the order of elements does not matter. The problems consist of a set of variables each of which must be assigned a value, subject to the particular constraints of the problem. Backtracking attempts to try all the combinations in order to obtain a solution. Its strength is that many implementations avoid trying many partial combinations, thus speeding up the running-time.

Backtracking is closely related to combinatorial search.

Implementation

Backtracking algorithms try each possibility until they find the right one. It is a depth-first search of the set of possible solutions. During the search, if an alternative doesn't work, the search backtracks to the choice point, the place which presented different alternatives, and tries the next alternative. When the alternatives are exhausted, the search returns to the previous choice point and tries the next alternative there. If there are no more choice points, the search fails.

This is usually achieved in a recursive function where each instance takes one more variable and alternatively assigns all the available values to it, keeping the one that is consistent with subsequent recursive calls. Backtracking is similar to a depth-first search but uses even less space, keeping just one current solution state and updating it. This pseudocode demonstrates the concept:

function backtrackingSearch() if all variables are assigned if the solution is valid return success and the solution else return failure else let "v" be an unassigned variable for each possible value "x" of "v" "v" ← "x" if backtrackingSearch() succeeds return success and the solution unassign "v" return failure

In order to speed up the search, when a value is selected, before making the recursive call, the algorithm either deletes that value from conflicting unassigned domains (forward checking) or checks all the constraints to see what other values this newly-assigned value excludes (constraint propagation). This is the most efficient technique for certain problems like 0/1 knapsack and n-queen problem. It gives better results than dynamic programming for these problems.

Heuristics

Several heuristics are common to speed up the process. Because the variables can be processed in any order, it is generally efficient to try the most constrained ones first (i.e. the ones with fewest value options) as this prunes the search tree early (maximizes the impact of the current "early" choice).

When choosing which value to assign, many implementations use forward checking to see which value restricts the least number of values, in the anticipation that such a choice is a) more likely to preserve a possible solution and b) a solution has been found when the number of outstanding constraints has been reduced to zero.

Sophisticated backtracking implementations often use a bounding function, which checks whether it is possible to obtain a solution, for the current partial solution. Thus, a bounding test that detects partial solutions that fail can improve search efficiency. Because it is run often, possibly at every step, the computational cost of bounding needs to be minimal, otherwise the overall efficiency of the algorithm is not improved. Effective bounding functions are created in a similar way to other heuristic functions - by relaxing the rules of the problem slightly.

When backtracking is used in a constraint programming language, an added overhead occurs since information about the constraints, used by the constraint solver itself, needs to be updated as well. In these languages, a simple depth-first search is an adequate implementation technique, as used in Planner and Prolog.

In addition to retaining minimal recovery values used in backing up, backtracking implementations commonly keep a variable trail, to record value change history. An efficient implementation will avoid creating a variable trail entry between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation.

An alternative to the variable trail is to keep a time stamp of when the last change was made to the variable. The time stamp is compared to the time stamp of a choice point. If the choice point has an associated time later than that of the variable, it is unnecessary to revert the variable when the choice point is backtracked, as it was changed before the choice point occurred.

Applications

Backtracking is used in the implementation of programming languages (such as Icon, Planner and Prolog) and other areas such as text parsing.

Backtracking is also utilized in the (diff) difference engine for the MediaWiki software.

Notes

References

* cite book
author = Gilles Brassard, Paul Bratley
title = Fundamentals of Algorithmics
publisher = Prentice-Hall
date = 1995

External links

* [http://www.hbmeyer.de/backtrack/backtren.htm interactive animation of a backtracking algorithm]

ee also

*Ariadne's thread (logic)
*Backjumping
* Recursion (computer science)


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Backtracking — Der Begriff Rücksetzverfahren oder englisch Backtracking (deut. Rückverfolgung) bezeichnet eine mathematische Problemlösungsmethode innerhalb der Algorithmik. Backtracking arbeitet nach dem Prinzip der Tiefensuche Inhaltsverzeichnis …   Deutsch Wikipedia

  • Backtracking — Trial and Error Verfahren; Rücksetzalgorithmus * * * Back|tra|cking 〈[bæ̣ktrækıŋ] n.; od. s; unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten… …   Universal-Lexikon

  • Backtracking — Retour sur trace Le retour sur trace, appelé aussi backtracking en anglais, consiste à revenir légèrement en arrière sur des décisions prises afin de sortir d un blocage. La méthode des essais et erreurs constitue un exemple simple de… …   Wikipédia en Français

  • backtracking — grįžimų metodas statusas T sritis informatika apibrėžtis Algoritmavimo metodas, kai sprendimas grindžiamas variantų tikrinimu ir, pasiekus aklavietę, grįžimu vienu žingsniu atgal. Grįžimų metodas labiausiai taikomas sprendžiant labirinto tipo… …   Enciklopedinis kompiuterijos žodynas

  • backtracking — The backwards movement of RNA polymerase along the DNA template to a state more stable than that encountered when some base pairs disrupt the attachment of the 3′ end from the active transcription site …   Medical dictionary

  • Backtracking — Back|tra|cking 〈[bæ̣ktrækıŋ] n.; Gen.: od. s; Pl.: unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten )Bestand gesichert (u. gegebenenfalls… …   Lexikalische Deutsches Wörterbuch

  • Backtracking — Suchmethode. 1. Prinzip: An denjenigen Punkten des Suchvorgangs, an denen zur Fortsetzung der Suche eine Auswahlentscheidung zwischen mehreren Möglichkeiten getroffen werden muss, wird zunächst der aktuelle Zustand festgehalten, bevor man die… …   Lexikon der Economics

  • backtracking — v. go backwards; retrace one s footsteps or path …   English contemporary dictionary

  • backtracking — backˈtracking noun • • • Main Entry: ↑back …   Useful english dictionary

  • Backtracking-Verfahren —   [ bæktrækɪȖ , englisch »sich zurückziehen«], Versuch und Irrtum …   Universal-Lexikon


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.