Back Tracking


In essence, BackTracking is most commonly used as a search technique. It goes roughly like this:
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.

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

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

View edit of September 15, 2010 or FindPage with title or text search