dict.org

The DICT Development Group


Search for:
Search type:
Database:

Database copyright information
Server information
Wiki: Resources, links, and other information


1 definition found
 for backtracking
From The Free On-line Dictionary of Computing (18 March 2015) :

  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">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)
  

Questions or comments about this site? Contact webmaster@dict.org