backtracking

(redirected from Backtracking search)
Also found in: Medical.

backtracking

[′bak‚trak·iŋ]
(computer science)
A method of solving problems automatically by a systematic search of the possible solutions; the invalid solutions are eliminated and are not retried.

backtracking

(algorithm)
A scheme for solving a series of sub-problems each of which may have multiple possible solutions and where the solution chosen for one sub-problem may affect the possible solutions of later sub-problems.

To solve the overall problem, we find a solution to the first sub-problem and then attempt to recursively solve the other sub-problems based on this first solution. If we cannot, or we want all possible solutions, we backtrack and try the next possible solution to the first sub-problem and so on. Backtracking terminates when there are no more solutions to the first sub-problem.

This is the algorithm used by logic programming languages such as Prolog to find all possible ways of proving a goal. An optimisation known as "intelligent backtracking" keeps track of the dependencies between sub-problems and only re-solves those which depend on an earlier solution which has changed.

Backtracking is one algorithm which can be used to implement nondeterminism. It is effectively a depth-first search of a problem space.
References in classic literature ?
And I told you, Mrs Merdle,' said Fanny, 'that if you spoke to me of the superiority of your son's standing in Society, it was barely possible that you rather deceived yourself in your suppositions about my origin; and that my father's standing, even in the Society in which he now moved (what that was, was best known to myself), was eminently superior, and was acknowledged by every one.
Winkle the interview Sam had so pathetically requested; but at length, when the conversation threatened to be interrupted by the unwelcome arrival of a third party, she hurriedly gave him to understand, with many professions of gratitude, that it was barely possible she might be in the garden an hour later, next evening.
It was barely possible to make out their great shapes in the gloom; but there they were.
For example, a backtracking search technique [4, 5] is a search based algorithm which systematically generates all possible solutions for the given NA-N board.
We can express the backtracking search as a recursive procedure ExtendRight: ExtendRight (PartialWord, node N in dawg, square) = if square is vacant then If N is a terminal node then LegalMove (PartialWord) for each edge E out of N if the letter l labeling edge E is in our rack and l is in the cross-check set of square then remove a tile l from the rack let N' be the node reached by following edge E let next-square be the square to the right of square ExtendRight (PartialWord .
For contributions to temporal reasoning, backtracking search algorithms, and constraint programming.
A human-level AI must either integrate, for example, backtracking search, partially observable Markov decision processes (POMDPs), logic theorem proving algorithms, productions systems, and neural networks, or it must be based on new, heretofore undiscovered computational methods that exhibit all of the best features of these computational methods.
Fahiem Bacchus (University of Toronto), the third invited speaker, presented his work on the use of caching in backtracking search.
Both texts cover the basics of constraint programming, such as local consistency and backtracking search methods, as well as more specialized topics like linear equations and temporal constraints.
For example, Bacchus and van Beek (1998) showed that rewriting k-ary CSPs as binary CSPs tended to decrease the time to solution of backtracking search, yet for the limited case of quasigroup completion, the powerful all-diff constraint propagation makes the k-ary representation superior.