Everything about Backtracking totally explained
Backtracking is a type of
algorithm that's a refinement of
brute force search. 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 doesn't 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's 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's generally efficient to try the most constrained ones first (for example 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's 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's run often, possibly at every step, the computational cost of bounding needs to be minimal, otherwise the overall efficiency of the algorithm isn't 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's 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's 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*a" will fail to match the sequence "aa" without backtracking (because, on the first pass, both "a"s are eaten by the "
*" leaving nothing behind for the remaining "
a" to match.)
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
Icon,
Planner and
Prolog) and other areas such as text
parsing.
Backtracking is also utilized in the (diff) difference engine for the
MediaWiki software.
Further Information
Get more info on 'Backtracking'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://backtracking.totallyexplained.com">Backtracking Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
