|
Backtracking is a type of algorithm that is a refinement of brute force search.[1] 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 1950s. In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ...
Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. ...
Derrick Henry Lehmer (February 23, 1905–May 22, 1991) was an American mathematician who refined Edouard Lucas work in the 1930s and devised the Lucas-Lehmer test for Mersenne primes. ...
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. To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. ...
Backtracking is closely related to combinatorial search. Combinatorial search is a branch of computer science that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. ...
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 try the next alternative there. If there are no more choice points, the search fails. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
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. A visual form of recursion known as the Droste effect. ...
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. One possible solution The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queens moves. ...
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). In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ...
Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ...
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. Look up Heuristic in Wiktionary, the free dictionary. ...
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. Constraint programming is a programming paradigm where relations between variables can be stated in the form of constraints. ...
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
Planner (often seen in publications as PLANNER) is a programming language designed by Carl Hewitt at MIT, and first published in 1969. ...
Prolog is a logic programming language. ...
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 The most widespread use of backtracking is in the execution of regular expressions. For example, the simple pattern "a*c" will fail to match the sequence "abc" without backtracking (because, on the first pass, the "bc" is eaten by the "*" leaving nothing behind for the remaining "c" to match.) In computing, a regular expression is a string that is used to describe or match a set of strings, according to certain syntax rules. ...
Another common use of backtracking is in Path Finding algorithms where the function traces over a graph of nodes and backtracks until it finds the least cost path.
Backtracking is used in the implementation of programming languages (such as Planner and Prolog) and other areas such as text parsing. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...
Planner (often seen in publications as PLANNER) is a programming language designed by Carl Hewitt at MIT, and first published in 1969. ...
Prolog is a logic programming language. ...
It has been suggested that Syntax analysis be merged into this article or section. ...
Notes - ^ Gurari, Eitan (1999). Backtracking algorithms CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms.
References - Gilles Brassard, Paul Bratley (1995). Fundamentals of Algorithmics. Prentice-Hall.
See also Ariadnes thread, named for the legend of Ariadne, is the term used to describe the solving of a problem with multiple apparent means of proceeding - such as a physical maze, a logic puzzle, or an ethical dilemma - through an exhaustive application of logic to all available routes. ...
External links - Example code of Backtracking, traversal coloring of a graph, in C++
|
Feeds |
Contact