Psychologie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

 
Backtracking: In der Informatik ist Backtracking eine algorithmische Technik, die dazu dient, systematisch Lösungen für Berechnungsprobleme zu finden. Dabei werden schrittweise Kandidaten für eine Lösung erstellt und falsche Entscheidungen rückgängig gemacht.

_____________
Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente.

 
Autor Begriff Zusammenfassung/Zitate Quellen

Peter Norvig über Backtracking – Lexikon der Argumente

Norvig I 87
Backtracking/Suchalgorithmen/künstliche Intelligenz/Norvig/Russell: Das Backtracking verbraucht weniger Speicherplatz [als die Tiefensuche]. (...) Es wird jeweils nur ein Nachfolger und nicht alle Nachfolger zeitgleich generiert; jeder teilweise expandierte Knoten merkt sich, welcher Nachfolger als nächstes generiert werden soll. Auf diese Weise wird nur O(m) Speicherplatz und nicht O(bm) benötigt (wobei m die maximale Knotentiefe ist). Die Backtracking-Suche ermöglicht einen weiteren speichersparenden (und zeitsparenden) Trick: die Idee, einen Nachfolger zu generieren, indem man die aktuelle Zustandsbeschreibung direkt ändert, anstatt sie zuerst zu kopieren. Dies reduziert den Speicherbedarf auf nur eine Zustandsbeschreibung und O(m) Handlungen. Damit dies funktioniert, müssen wir in der Lage sein, jede Änderung rückgängig zu machen, wenn wir zurückkehren, um den nächsten Nachfolger zu generieren.
Norvig I 228
Die Idee der Backtracking-Suche geht auf Golomb und Baumert (1965)(1) zurück, und ihre Anwendung auf die constraint satisfaction ist auf Bitner und Reingold (1975)(2) zurückzuführen, obwohl sie den grundlegenden Algorithmus bis ins 19. Jahrhundert zurückverfolgen. Bitner und Reingold führten auch die MRV heuristic (MRV = minimum remaining values) ein, die sie die most-constrained-variable heuristic nannten. Brelaz (1979)(3) nutzte degree heuristic als Tiebreaker, nachdem er die MRV heuristic angewendet hatte. Der resultierende Algorithmus ist trotz seiner Einfachheit immer noch die beste Methode zur k-Färbung beliebiger Graphen. Haralick und Elliot (1980)(4) schlugen die least-constraining-value heuristic vor.
Norvig I 229
Die grundlegende Backjumping-Methode ist John Gaschnig (1977(5), 1979(6)) zu verdanken. Kondrak und van Beek (1997)(7) zeigten, dass dieser Algorithmus im Wesentlichen durch Forward Checking subsumiert wird.
Konfliktgesteuertes Backjumping wurde von Prosser (1993)(8) entwickelt. Die allgemeinste und leistungsfähigste Form des intelligenten Backtracking wurde eigentlich sehr früh von Stallman and Sussman (1977)(9) entwickelt. Ihre Technik des abhängigkeitsgesteuerten Backtrackings führte zur Entwicklung von truth maintenance systems (Doyle, 1979)(10) (...). Die Verbindung zwischen den beiden Bereichen wird von de Kleer (1989(11)) analysiert.
Für Vorwärtsverkettung, Rückwärtsverkettung: siehe >Software-Agenten/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.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.

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

Send Link

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


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