 |
|||
| HSG |
|
(Versuch einer) Definition
Beim 'Durchforsten' der Wissensbasis von oben nach unten und von links nach rechts stößt das Prolog-System auch an Stellen, wo weitere Alternativen möglich sind. Diese Stellen werden markiert. Beim Backtracking wird bis zu der nächsten markierten Stelle zurückgegangen und die nächste noch nicht begangene Alternative gewählt. Beim Backtracking in Prolog werden die Variablenbindungen, die seit der markierten Stelle gemacht wurden, rückgängig gemacht.
Veranschaulichung
Kommt man beim Durchlaufen des Baums an die Verzweigung V1, so kann man, bevor man den Weg links nimmt, eine 'Backtracking-Markierung' hinterlassen, die zeigt, welcher Weg genommen wird und welche Wege noch nicht begangen wurden. Außerdem wird man sich merken, dass es noch nicht begangene Alternativen gibt. Das macht man bei der nächsten Verzweigung V2 genauso. Dann erreicht man das Blatt A. Da man weiß, dass es weitere Möglichkeiten gibt, geht man bis zur nächsten Markierung in V2 zurück und nimmt den nächsten Weg. War man bei B, so weiß man doch, dass es weitere Möglichkeiten gibt und geht zurück nach V2. Dort sieht man, dass alle Alternativen erschöpft sind, also geht man weiter bis V1 zurück und wählt die nächste freie Möglichkeit. So geht das dann weiter, bis alle Wege begangen sind.
Details zum Backtracking
Mit der Wissenbasis
p(a). p(b). c:-p(X).
reagiert Prolog auf die Anfrage ?- c. mit yes. Ein Trace zeigt, dass sich das System mit der Ersetzung p(a) zufriedengibt. b wird also nicht in p eingesetzt. Das liegt daran, dass das Prädikat c nullstellig ist. Schreibt man c(X):-p(X), so werden alle Möglichkeiten für X getestet und ausgegeben.
Dieses Backtracking kann man auch mit dem Prädikat fail erzwingen, wie folgende Wissensbasis zeigt:
p(a). p(b). c:-p(X),fail. c:-p(X).
Bitte mit trace. überprüfen!
Links
- Backtracking - wikipedia
- Backtracking - engl. wikipedia
