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.
(1995-04-13)
Nearby terms:
backslash « backspace « backtick « backtracking »
backup » Backup Domain Controller » backup pumpkin
