| Backtracking-Verfahren (Trial-and-Error-Verfahren):
Bezeichnung für ein Lösungsverfahren, bei dem man versucht,eine Teillösung eines Problems systematisch zu einer Gesamtlösung auszubauen. Falls in einem gewissen Stadium ein weiterer Ausbau einer vorliegenden Lösung nicht mehr möglich ist (Sackgasse), werden einer oder mehrere der letzten Teilschritte rückgängig gemacht. Die dann erhaltene reduzierte Teillösung versucht man auf einem anderen Weg wieder auszubauen. Das Zurücknehmen von Schritten und erneute Vorangehen wird solange wiederholt, bis eine Lösung des vorliegenden Problems gefunden ist oder bis man erkennt, daß das Problem keine Lösung besitzt. Die Möglichkeit in Sackgassen zu laufen und aus ihnen wieder herauszufinden, zeichnet das Backtracking-Verfahren aus. |
| Die Teilziele einer Frage oder innerhalb einer Regel werden von links
nach rechts zu erfüllen versucht. Erst wenn ein Teilziel erfüllt
ist, wird zum nächsten übergegangen. Werden bei der Erfüllung
eines Teilzieles Variablen gebunden, so sind die Variablen mit gleichen
Namen auch in den folgenden Teilzielen an dieselben Werte gebunden.
Wenn ein Teilziel (B) nicht erfüllt werden kann, wird zum vorhergehenden Teilziel (A) zurückgegangen. Die Variablen, die zuvor bei der Erfüllung dieses Teilzieles (A) gebunden waren, werden wieder zu freien Variablen. Es wird eine weitere Lösung für dieses Teilziel (A) gesucht. Mit einer gefundenen Lösung wird dann wieder versucht, das nächste Teilziel (B) zu erfüllen. Das Backtracking kann auf zwei Weisen terminieren:
|
|
|
|