|
 Definitions for backtracking: The Free On-line Dictionary of Computing (27 SEP 03)
:
backtracking
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)
Related SitesBacktracking - Wikipedia, the free encyclopedia
Backtracking is a general algorithm for finding all (or some) solutions to some ... Backtracking is also utilized in the (diff) difference engine for the ...
backtracking: Definition from Answers.com
backtracking ( baktraki ) ( computer science ) A method of solving problems automatically by a systematic search of the possible solutions; the
Backtracking
... feature of regular expression matching involves the notion called backtracking. ... Here is an example of backtracking: Let's say you want to find the word ...
Algorithmics of sudoku - Wikipedia, the free encyclopedia
1 Solving sudokus by backtracking. 2 Exact Cover in solving sudokus ... 7.3 Example of a back-tracking Sudoku solver (in Ruby programming language) ...
Runaway Regular Expressions: Catastrophic Backtracking
This is the reason why your regular expression takes forever, or crashes your program. ... Backtracking again, the first x+ in the group's first iteration ...
Backtracking
We will develop a backtracking algorithm to try to solve this problem. ... In backtracking we perform a depth-first traversal of this tree until we reach a ...
|
