Back Tracking

See http://en.wikipedia.org/wiki/Backtracking

In essence, BackTracking is most commonly used as a search technique. It goes roughly like this:

• Make a choice
• Compute the consequences
• If the search is unsuccessful or needs to continue for some other reason,
  • Undo the consequences,
  • Undo the choice
  • Make a different choice
  • LatherRinseRepeat

---

A programming technique used in ArtificialIntelligence to achieve a goal by BruteForce by trying out all the possibilities. It usually is implemented DepthFirst.

Used primarily in games.

---

Doesn't strike me as quite right... it's more that an algorithm may reach a point that it is known that there's no point continuing down that train of logic, and therefore backtracks to a previous branch and tries another leg.

Yes, that's closer. The previous attempted definition perhaps is of ExhaustiveBacktracking?. It's also false that it's used primarily in games. I'm not sure that it is relevant that it is "usually implemented depth first", because often other orderings would do as well or better, but depth first is better supported by most languages. There's nothing inherently about back tracking that makes depth first most suitable. And considering chess as an example, actually, people go to some trouble to do BreadthFirst. I'm not sure depth first is necessarily the most common implementation.

My professor told the class that originally LISP used a breadth first search, but they changed it to depth first and were amazed that is was faster. He explained it like if the solution is at level 17 of the tree, using a breadth first search you'd have to try all the combinations up to level 16 in order to solve. But if it was depth first you could go directly to level 17.

• There are several things very seriously wrong with this account. Either your professor was extremely confused, or your memory is very hazy, or both.

---

Languages and algorithms which support/use BackTracking natively, either explicitly (through a "choice/fail" mechanism, or similar) or implicitly

• OzLanguage
• IconLanguage
• PrologLanguage and other LogicProgrammingLanguages
• RegularExpressions (the so-called NFA (NondeterministicFiniteAutomata?) kind, that is. I'm speaking of the grep-derived, perl-enhanced feature found in many languages, which (almost?) is a language in and of itself, not the mathematical concept of a RegularExpression. NFA regex engines use backtracking to do string matching. DeterministicFiniteAutomata?, on the other hand, do not use backtracking)
• RecursiveDescent parsers
  • But not always. Memoization can be used instead.

---

I guess Oz is somewhat special, cause choice/fail are built on top of a more simple Oz, they're not a basic thing. Considering this, it can be pointed out that every language that has an AmbSpecialForm, (or where it can be easily built) has backtracking.

Every language that has loops has backtracking. At its most basic, backtracking is just the continue statement in C. Loops are the choice points. Simple example for finding pythagorean triples:

   #include <stdio.h>
   int main (int argc, char * const argv[]) {
       int numresults = 100;
       for (int c = 1; ; ++c) {
           for (int a = 1; a <= c; ++a) {
               for (int b = a; b <= c; ++b) {
                   if (a*a + b*b != c*c) 
                       continue; // failed, so backtrack
                   printf("a %3d   b %3d   c %3d\n", a, b, c);
                   if (--numresults == 0) return 0; // terminate
               }
           }
       }
   }

---

See: FiniteStateMachine

---

CategorySolutions