Peter Norvig on Backtracking - Dictionary of Arguments
Norvig I 87
Backtracking search/search algorithms/artificial intelligence/Norvig/Russell: Backtracking uses less memory [than depth-first search]. (…) only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next. In this way, only O(m) memory is needed rather than O(bm) (hwere m is the maximum depth of any node). Backtracking search facilitates yet another memory-saving (and time-saving) trick: the idea of generating a successor by modifying the current state description directly rather than copying it first. This reduces the memory requirements to just one state description and O(m) actions. For this to work, we must be able to undo each modification when we go back to generate the next successor.
Norvig I 228
The idea of backtracking search goes back to Golomb and Baumert (1965)(1), and its application to constraint satisfaction is due to Bitner and Reingold (1975)(2), although they trace the basic algorithm back to the 19th century. Bitner and Reingold also introduced the MRV heuristic, which they called the most-constrained-variable heuristic. Brelaz (1979)(3) used the degree heuristic as a tiebreaker after applying the MRV heuristic. The resulting algorithm, despite its simplicity, is still the best method for k-coloring arbitrary graphs. Haralick and Elliot (1980)(4) proposed the least-constraining-value heuristic.
Norvig I 229
The basic back jumping method is due to John Gaschnig (1977(5), 1979(6)). Kondrak and van Beek (1997)(7) showed that this algorithm is essentially subsumed by forward checking.
Conflict-directed back jumping was devised by Prosser (1993)(8). The most general and powerful form of intelligent backtracking was actually developed very early on by Stallman and Sussman (1977)(9). Their technique of dependency-directed backtracking led to the development of truth maintenance systems (Doyle, 1979)(10) (…). The connection between the two areas is analyzed by de Kleer (1989(11)).
For forward chaining, backward chaining: see >Software agents/Norvig.
1. Golomb, S. and Baumert, L. (1965). Backtrack proramming. JACM, 14, 516–524.
2. Bitner, J. R. and Reingold, E. M. (1975). Backtrack programming techniques. CACM, 18(11), 651–656.
3. Brelaz, D. (1979). New methods to color the vertices of a graph. CACM, 22(4), 251–256.
4. Haralick, R. M. and Elliot, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. AIJ, 14(3), 263–313.
5. Gaschnig, J. (1977). A general backtrack algorithm that eliminates most redundant tests. In IJCAI-77, p. 457.
6. Gaschnig, J. (1979). Performance measurement and analysis of certain search algorithms. Technical report CMU-CS-79-124, Computer Science Department, Carnegie-Mellon University.
7. Kondrak, G. and van Beek, P. (1997). A theoretical evaluation of selected backtracking algorithms. AIJ, 89, 365–387.
8. Prosser, P. (1993). Hybrid algorithms for constraint satisfaction problems. Computational Intelligence, 9, 268–299.
9. Stallman, R.M. and Sussman, G. J. (1977). Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. AIJ, 9(2), 135–196
10. Doyle, J. (1979). A truth maintenance system. AIJ, 12(3), 231–272.
11. de Kleer, J. (1989). A comparison of ATMS and CSP techniques. In IJCAI-89, Vol. 1, pp. 290–296._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010