5.2.4.2 Backtracking

Backtracking ist eine weit verbreitete Methode zur Problemlösung,^5.40 die bereits sehr früh entwickelt und danach wiederholt neu eingeführt wurde. Bitner und Reingold (1975, S. 651) führen Lucas (1891) als eine frühe Quelle der Beschreibung einer solchen Methode zum Durchqueren von Irrgärten und Labyrinthen an. Backtracking kommt derzeit in vielen Varianten zum Lösen von kombinatorischen Problemen zum Einsatz. Es stellt eine Verbesserung gegenüber naivem Generate & Test dar, weil bei diesem Verfahren die Variablen nach und nach belegt werden und Inkonsistenzen frühzeitig erkannt werden können. Es wird eine Variable nach der anderen ausgewählt und mit einem Wert aus ihrem Wertebereich belegt. Anschließend wird jeweils anhand der vorhandenen Constraints überprüft, ob die vorher bereits belegten Variablen mit dem neuen Variablenwert ,,kompatibel`` zueinander, d.h. konsistent, sind. Wenn der zugewiesene Wert ein Constraint verletzt, wird der nächste Wert aus dem Wertebereich der aktuellen Variable ausgewählt und die Variable entsprechend mit diesem Wert belegt. Dies geschieht solange, bis alle Werte aus dem Wertebereich probiert oder ein kompatibler Wert gefunden wurde, und die nächste Variable belegt werden kann. Gibt es keinen Wert im Wertebereich, der nicht schon getestet wurde, wird eine Ebene zurückgegangen (engl. backtracking) und der zuvor belegten Variable ein alternativer Wert aus deren Wertebereich zugewiesen. Die Zurücknahme der jeweils letzten Wertezuweisung wird chronologisches Backtracking (BT) genannt.^5.41

Backtracking erweitert somit eine konsistente Teillösung nach und nach zu einer vollständigen Lösung, sofern eine Lösung existiert. Werden alle Alternativen durchprobiert, ohne dass eine konsistente Belegung gefunden werden kann, ist das Constraint-Netz inkonsistent und es gibt keine Lösung für das CSP.

Abbildung 5.13: Beispiel für einen Suchbaum

Die Suche im Lösungsraum lässt sich als gerichteter Graph, einem Suchbaum, darstellen, der von dem Lösungsalgorithmus durchlaufen wird. Jeder Knoten und jedes Blatt dieses Suchbaums repräsentiert die Belegung einer Variablen mit einem Wert. Der Suchbaum besitzt genau so viele Ebenen wie das CSP Variablen. In jeder Ebene wird jeweils eine Variable mit Werten belegt. Eine Lösung ist ein Pfad durch diesen Suchbaum, auf dem alle Variablen mit zueinander konsistenten Werten bzgl. der Constraints belegt sind. In Abbildung 5.13 ist der vollständige Suchbaum zu dem Constraint-Beispiel aus Abschnitt 3.6.3 f. dargestellt. Die gefüllten Kreise stellen legale Zustände bzgl. der Belegung der Constraint-Variablen P_FSB_Rate, MB_FSB_Rate und S_FSB_Rate dar. Terminale legale Zustände sind durch ein gefülltes Dreieck gekennzeichnet. Die durch unterbrochene Kanten verbundenen Kästchen stellen illegale Zustände (Inkonsistenzen) dar. Sie entstehen, wenn die Belegung einer Variable mit einem Wert fehlschlägt. Lässt sich aus einem Zustand heraus für einen Nachfolger keine legale Wertebelegung finden, spricht man von einem terminalen illegalen Zustand bzw. einem dead-end, gekennzeichnet durch ein gefülltes Kästchen (siehe Abbildung 5.14).

Abbildung 5.14: Beispiel für chronologisches Backtracking

Selbst ein einfacher Algorithmus, der den Suchbaum aus Abbildung 5.13 von links nach rechts aufspannt, würde sofort eine Lösung ohne Backtracking generieren können: P_FSB_Rate = 66, MB_FSB_Rate = 66 und S_FSB_Rate = 66. Backtracking wird immer dann notwendig, wenn in dem Wertebereich einer Variable kein konsistenter Wert zu den bereits belegten Variablen gefunden werden kann:

Beispiel 5.2.4   Angenommen, es sind keine Mainboards zugelassen, die einen Front-Side-Bus von 66MHz zur Verfügung stellen. Der Wertebereich des Parameters MB_FSB_Rate enthält demnach ausschließlich die Werte 100 und 133. In Abbildung 5.14 ist beispielhaft das Backtracking für diesem Fall dargestellt. Die Belegung von P_FSB_Rate mit 66 ist hier ein terminaler illegaler Zustand, da alle seine Nachfolger Inkonsistenzen bzgl. der vorliegenden Constraints zur Folge hätten. Nachdem der Suchalgorithmus nacheinander die beiden möglichen Werte für MB_FSB_Rate durchprobiert und Inkonsistenzen zur Belegung von P_FSB_Rate festgestellt hat, wird der Suchvorgang mit den beiden weiteren Werten für P_FSB_Rate fortgesetzt.

In Abbildung 5.15 ist ein einfacher Algorithmus für chronologisches Backtracking von Dechter und Frost (1998, S. 13) dargestellt. Der Algorithmus besteht aus drei Phasen: (1) einer vorwärtsgerichteten Phase, in der die nächste Variable $v_{cur}$ entsprechend der Ordnung ausgewählt wird, (2) einer Phase, in der die aktuelle Teillösung um einen konsistenten Wert für $v_{cur}$ erweitert wird, sofern es diesen gibt und (3) einer rückwärtsgerichteten Phase, in der, falls kein konsistenter Wert für $v_{cur}$ existiert, zur vorherigen Variable zurückgekehrt wird. Mit $\vec{a}_i$ wird eine Teillösung, d.h. das Tupel fortlaufender Werte $(a_1,\ldots,a_i)$ einer partiellen Belegung bezogen auf die gegebene Ordnung der Variablen $v_1,\ldots,v_i$ bezeichnet. Zu beachten ist, dass der Algorithmus genau eine Lösung, die erste, auf die er stößt, zurückgibt. Kann keine Lösung gefunden werden, wird festgestellt, dass das Constraint-Netz inkonsistent ist.

Abbildung 5.15: Backtracking-Algorithmus (vgl. Dechter und Frost, 1998, S. 13)

Ein Algorithmus, der mehrere Lösungen bzw. alle Lösungen eines Constraint-Netzes zurückgeben soll, müsste dahingehend erweitert werden, dass er letztendlich den gesamten Suchbaum durchläuft. Die Reihenfolge, in der Lösungen gefunden werden, ergibt sich in Abhängigkeit von der Struktur des Suchbaums und dementsprechend aus der Ordnung der Variablen, anhand der dieser Baum generiert bzw. durchlaufen wird. Soll schnellstmöglich irgendeine Lösung gefunden werden, kann es entscheidend sein, in welcher Reihenfolge die Variablen bzw. die Werte der Variablen ausgewählt werden. Bei einer günstigen Reihenfolge kann u.U. das Testen einer großen Anzahl inkompatibler Belegungen vermieden werden, bevor eine Lösung gefunden wird. Zur Bestimmung der Reihenfolge, in der Variablen mit Werten belegt werden, wurde eine Vielzahl von Heuristiken entwickelt, auf die in Abschnitt 5.2.5 ff. eingegangen wird.

Chronologisches Backtracking ist eine vollständige Suche, die systematisch den gesamten Suchraum durchläuft und dabei keinerlei Nutzen aus den Constraints zieht. Dabei ist Backtracking sowohl vollständig (alle Lösungen können gefunden werden) als auch korrekt (alle gefundenen Lösungen erfüllen die Constraints) (vgl. Tsang, 1993, S. 120). Das Laufzeitverhalten von Backtracking ist allerdings für die meisten nichttrivialen Probleme exponentiell vgl. Barták, 1999a, S. 557; Tsang, 1993, S. 152.

Der Vorteil von Backtracking gegenüber einfachem Generate & Test liegt auf der Hand: Nach jeder Belegung einer Variablen mit einem Wert wird überprüft, ob die Belegung mit den bisherigen Zuweisungen konsistent ist. Erst danach werden weitere Variablen mit Werten belegt. Von Nachteil ist, dass nicht überprüft wird, ob die Wertebelegung evtl. mit später zu belegenden Variablen kollidiert. Dies führt dazu, dass falsch ausgewählte Werte u.U. erst zu einem sehr späten Zeitpunkt entdeckt werden. Abhilfe kann durch look-ahead-Strategien geschaffen werden. Ein weiterer Nachteil ist das sog. (engl.) trashing, womit der Umstand bezeichnet wird, wenn die Suche ggf. in unterschiedlichen Bereichen des Suchraums wiederholt aus denselben Gründen fehlschlägt (vgl. Mackworth, 1977a, S. 100). Dieser und weiterer redundanter Suchaufwand kann mittels look-back-Strategien vermieden werden. Nachfolgend werden einige Backtracking-Varianten aufgezeigt, welche die Nachteile von einfachem chronologischem Backtracking reduzieren.

Fußnoten

...^5.40

Prolog nutzt z.B. Backtracking zur Beantwortung von Anfragen.

...^5.41

Dieses einfache Suchverfahren entspricht einer Tiefensuche.