Backtracking
|
|
Backtracking is a strategy for finding solutions to constraint satisfaction problems. These are problems with a complete solution, whereby 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.
| Contents |
Implementation
Essentially, the idea is to try each possibility until you get the right one. It is a depth-first search of the set of solutions. During the search, if you try an alternative that doesn't work, you backtrack to the choice point, the place which presented you with different alternatives, and you try the next alternative. When you have exhausted the alternatives, you return to the previous choice point and try the next alternative there. If there are no more choice points, the search fails.
This is usually achieved in a recursive function whereby 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.
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-assinged value excludes (constraint propagation).
Heuristics
Several heuristics are common to speed up the process. Because the variables can be processed in any order, it generally makes sense to try the most constrained ones first (ie. the ones with fewest options for values) as this prunes the search tree early. When choosing which value to assign, many implementations use a form of forward checking to see which value restricts the least number of future values. The philosophy behind this is to choose values that are more likely to obtain a solution quicker.
Sophisticated backtracking implementations often use a bounding function. This is specific to the problem examined and is run at every assignment step, to check whether it is still possible to obtain a solution. Thus, a simple test that immediately detects a number of partial solutions that will certainly fail, may end up cutting down the search by 99%. Because it is run at every step in what is often an exponential search space, the bounding function needs to be quite easily computable, otherwise the algorithm is no better off. Good 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, it has an added complication that the information stored about the constraints needs to be updated as well. In these languages, a simple depth first search is an adequate implementation technique, as it is in Planner and Prolog. In implementing backtracking, it is common to keep a variable trail, to record the changes in the values of a particular variable. A smart implementor will avoid creating a variable trail between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation.
An alternate 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 like Prolog and other areas such as text parsing.
See also
Actor modelde:Backtracking fr:Retour sur trace it:Backtracking