backtracking
<algorithm> A scheme for solving a series of subproblems each of which
may have multiple possible solutions and where the solution chosen for one
subproblem may affect the possible solutions of later subproblems.
To solve the overall problem, we find a solution to the first subproblem and
then attempt to recursively solve the other subproblems 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 subproblem and so on. Backtracking
terminates when there are no more solutions to the first subproblem.
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 subproblems and only
resolves 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 depthfirst search of a problem space.
(19950413)
Nearby terms:
backslash « backspace « backtick « backtracking
» backup » Backup Domain Controller » backup pumpkin
