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.
6,157,922) for the company's transparent Backtracking technology.
Rather than analyzing all possible alternatives prior to choosing a solution, a system using backtracking generally investigates one alternative at a time until an acceptable solution is found.
Invented by Trilogy software developer, Paul Vaughan, Trilogy's Backtracking technology, the first of its kind, enables software modelers working with general purpose computer languages, such as C++ and Java, to write object oriented configuration solutions intuitively without imposing control flow limitations on the search program.
Since Trilogy's Backtracking technology makes it easy to carry out complex configurations on the Web by automating the entire backtracking process, it is of critical importance to large companies selling complex products through multiple sales channels.