backtracking


Also found in: Dictionary, Thesaurus, Medical, Wikipedia.

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 periodicals archive ?
The only reason they're backtracking is the negative reaction from the neighbors,'' Ian Pari, a senior city traffic engineer, said of the developer.
Along the journey, she writes, companies can expect to face pains that may be more or less chronic--and organizations and leaders dealing with them "will need to engage in a constant dance of moving forward and backtracking, recalibrating and moving on.
net--permitted multiple go-rounds, backtracking, and stopovers at will.
He was looking for a certain trail but couldn't find it, despite backtracking his path twice.
This seems like another piece of backtracking by the First Minister.
Backtracking inside the Beltway would add to the isthmus's dual challenges: slow growth and collapsing commodity prices.