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 rest of discussion will focus on the backtracking number to be k =50%N and 75%N only.
Furthermore, regardless of the number of backtracking (k=50%N or 75%N), from Fig.
Either KDA or KDR is used with k backtrackings to search for the NN.
The number of backtrackings, k, were 25%, 50% and 75% of N, respectively.
The types of data (uniform or normal generated), the number of data, and number of backtrackings (50%N and 75%N) are considered together.
However, a number of backtrackings that is 80% of the data amount or more defeats the purpose of multiple KD-trees, which is a lower number of backtrackings and a high accuracy rate.
In accordance with the previous conclusion, KDA10 is more suited to feature matching on image stitching, when the number of backtrackings is 60% of the data amount, as suggested.