browse words by letter
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

  1  definition  found 
 
  From  The  Free  On-line  Dictionary  of  Computing  (13  Mar  01)  [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) 
 
 

Recent Content

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Shared content with implied attribution.