Backtracking

1 definition found

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  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)