By Letter: Non-alphabet | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
  Email this page to a friend


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.



< Previous Terms Terms Containing backtracking Next Terms >
back quote
backside cache
backslash
backspace
backtick
backtracking
Charme
CONNIVER
CORAL
Delta-Prolog
backup
Backup Domain Controller
backup pumpkin
backup software
Backus-Naur Form


Web Standards & Support:

Link to and support eLook.org Powered by LoadedWeb Web Hosting
Valid XHTML 1.0!Valid CSS!eLook.org FireFox Extensions