Economics Dictionary of Arguments

Home Screenshot Tabelle Begriffe

Author Item Summary Meta data

Stuart J. Russell 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). 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.

Russell I
B. Russell/A.N. Whitehead
Principia Mathematica Frankfurt 1986

Russell II
B. Russell
The ABC of Relativity, London 1958, 1969
German Edition:
Das ABC der Relativitätstheorie Frankfurt 1989

Russell IV
B. Russell
The Problems of Philosophy, Oxford 1912
German Edition:
Probleme der Philosophie Frankfurt 1967

Russell VI
B. Russell
"The Philosophy of Logical Atomism", in: B. Russell, Logic and KNowledge, ed. R. Ch. Marsh, London 1956, pp. 200-202
German Edition:
Die Philosophie des logischen Atomismus
Eigennamen, U. Wolf (Hg), Frankfurt 1993

Russell VII
B. Russell
On the Nature of Truth and Falsehood, in: B. Russell, The Problems of Philosophy, Oxford 1912 - Dt. "Wahrheit und Falschheit"
Wahrheitstheorien, G. Skirbekk (Hg), Frankfurt 1996

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link
> Counter arguments against Russell

Authors A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z  

Concepts A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z