next up previous contents index
Nächste Seite: 5.2.4.7 Hybride Ansätze Aufwärts: 5.2.4 Suchverfahren Vorherige Seite: 5.2.4.5 Backtracking mit Forward   Inhalt   Index

5.2.4.6 Backtracking mit Look-Ahead

In der Literatur wird zwischen der Strategie des Partial Look-Ahead (PLA) und der des Full Look-Ahead (FLA) unterschieden (vgl. Haralick und Elliot, 1980, S. 267). Backtracking-Algorithmen, die während des Suchvorgangs Full Look-Ahead einsetzen, werden auch Maintaining Arc Consistency (MAC) genannt, unter diesem Namen vorgestellt von Sabin und Freuder (1994b,a).5.50 Beide Strategien sind eine Weiterführung des Forward Checking. Der Unterschied besteht darin, dass die in jedem Schritt des Suchalgorithmus hergestellte lokale Konsistenz eine höhere Form von Kantenkonsistenz als beim FC ist. Während ein Suchalgorithmus mit PLA in jedem Schritt gerichtete Kantenkonsistenz herstellt (DAC), wird im Verlauf einer Suche mit FLA bzw. MAC in jedem Schritt ein Algorithmus aufgerufen, der vollständige Kantenkonsistenz (AC) für die bisher noch unbelegten Variablen herstellt.5.51

Der Unterschied von PLA und FLA zu FC besteht demnach in dem Umfang der Propagation der Variablenwerte und einer erhöhten Anzahl von Konsistenztests. Während FC ausschließlich die Konsistenz zwischen der aktuellen Variable und mit dieser über ein Constraint in direkter Verbindung stehender Variablen überprüft, werden durch PLA und FLA auch diejenigen Variablen berücksichtigt, die nicht unmittelbar von der aktuellen Variable eingeschränkt werden. Wenn durch diese vermehrte Propagation eine Domäne keine Werte mehr enthält, bedeutet dies wie beim FC, dass das Problem mit der aktuellen Teilbelegung nicht lösbar ist und ein Backtracking ausgelöst werden muss. Ein allgemeines Ablaufschema von look-ahead-Algorithmen ist in Abbildung 5.17 zu sehen.

Abbildung 5.17: Ablaufschema von look-ahead-Algorithmen (vgl. Tsang, 1993, S. 126)
\begin{figure}\centering
\includegraphics[width=10.75cm]{images/constraints_look-ahead}
\ifx\pdfoutput\undefined
\fi
\end{figure}

Da PLA und FLA bzw. MAC in jedem Schritt der Suche einen höheren Konsistenzgrad als FC herstellt, werden durch diesen Algorithmus mehr inkonsistente Werte herausgefiltert, und der Suchraum dadurch stärker reduziert. Allerdings erhöht sich durch die gestiegene Anzahl Konsistenztests ebenfalls der Berechnungsaufwand dieses Verfahrens, so dass der Aufwand für die Herstellung eines Konsistenzgrades größer werden kann, als der erzielte Gewinn durch die Reduzierung des Suchraums (vgl. Güsgen, 2000, S. 279). Dies kann auch darin resultieren, dass die genannten look-ahead-Algorithmen bei bestimmten Problemstellungen mehr Aufwand als normales Backtracking ohne look-ahead benötigen (vgl. Barták, 1999a, S. 559).5.52 Es gilt einen Kompromiss zwischen einem möglichst hohem Konsistenzgrad und damit Ausschluss möglichst vieler inkonsistenter Werte, und einem geringen Overhead des Konsistenzalgorithmus zu finden. Generell gilt, wie bereits in Abschnitt 5.2.3.5 zu Konsistenzverfahren angesprochen, dass sich das Herstellen eines höheren Konsistenzgrades in Abhängigkeit von dem Problem immer dann lohnt, je stärker sich die Variablen eines CSP gegenseitig beschränken, so dass sich die Domänen der Variablen durch die angewendeten Konsistenzverfahren um eine möglichst hohe Anzahl Werte reduzieren lassen (vgl. Tsang, 1993, S. 136).

Um festzustellen, welcher Konsistenzgrad am besten geeignet ist, einen Suchalgorithmus zu verbessern, ist allerdings eine genauere Betrachtung des konkreten Problems erforderlich. Von Haralick und Elliot (1980) wurde die Performanz verschiedener Suchverfahren zur Lösung von CSPs empirisch untersucht und festgestellt, dass die Verwendung von FC aufgrund der geringeren Anzahl von Konsistenztests zu einem besseren Laufzeitverhalten führt. Die Herstellung von höheren Konsistenzgraden zahlt sich demnach i.A. nicht aus. Lange Zeit haben diese und weitere Untersuchungen dazu geführt, dass look-ahead-Mechanismen, die mehr Konsistenztests als FC durchführen, grundsätzlich als weniger effektiv angesehen wurden, und FC sich zum Standard-Suchverfahren für CSPs etablieren konnte. Ursache hierfür war allerdings das fehlende Verständnis für das Verhalten von Suchalgorithmen auf unterschiedlich strukturierten CSPs (vgl. Grant und Smith, 1995, S. 4). So wurden empirische Untersuchungen lange Zeit überwiegend auf CSPs mit relativ wenigen Variablen5.53 und hoher Constraint-Dichte durchgeführt, wie z.B. dem n-Damen-Problem5.54 (vgl. Haralick und Elliot, 1980, S. 274 ff.) und dem Zebra-Problem vgl. Dechter, 1990a, S. 308; Prosser, 1993b, S. 290 ff.; Smith, 1992, S. 37. Ein FC-Suchalgorithmus ist hier Lösungsverfahren mit höherem Konsistenzgrad überlegen, da weniger Konsistenztests vorgenommen werden, und der Overhead durch das Konsistenzverfahren relativ gering ist. FLA- bzw. MAC-Algorithmen sind für derart strukturierte CSPs, bedingt durch die in diesem Fall hohen look-ahead-Kosten, weniger gut geeignet (vgl. Grant und Smith, 1996, S.  179). Es gibt allerdings eine Vielzahl von Problemen, in denen Verfahren mit mehr look-ahead dem einfachen FC überlegen sind. Frost und Dechter (1996a,b) stellen daher einige Varianten vor, die FC und FLA in einem Algorithmus vereinen und beides jeweils nach Bedarf einsetzen.

Mehr Aufwand durch look-ahead ist dann besonders sinnvoll, wenn ein stark beschränktes Problem mit niedriger Constraint-Dichte vorliegt, so dass der Overhead des Konsistenzverfahrens aufgewogen wird mit dem Gewinn durch die Reduktion des Suchraums (vgl. Bessière und Régin, 1996, S. 7). Ein solches CSP besteht im Idealfall aus relativ wenigen Constraints, in dem allerdings die vermehrte Propagation dazu führt, dass die Domänen der Variablen stark eingeschränkt werden können. Neuere Untersuchungen haben gezeigt, dass insbesondere aktuelle MAC-Algorithmen (vgl. Sabin und Freuder, 1997), die einen höheren Konsistenzgrad als FC herstellen, für zufällig generierte CSPs, die stark beschränkt und umfangreicher sind, als die von Haralick und Elliot (1980) untersuchten, die bessere Wahl darstellen (vgl. Gent und Prosser, 2000; Bessière und Régin, 1996; Frost und Dechter, 1996a; Grant und Smith, 1996; Sabin und Freuder, 1994a).5.55 Je umfangreicher das zu lösende Problem, umso eher lohnt sich demnach die Herstellung eines höheren Konsistenzgrades zur Problemreduktion und Vereinfachung der Lösungssuche.5.56 Insgesamt muss aber festgehalten werden, dass kein Verfahren dem anderen grundsätzlich überlegen ist. Jedes verfügt über Vorteile in bestimmten Bereichen, da ihr Verhalten problemabhängig von der Struktur des CSP ist. Während die Anwendung von FC bei CSPs mit hoher Constraint-Dichte und schwacher Beschränkung zu empfehlen ist, sollten MAC-Algorithmen eher bei CSPs mit geringerer Constraint-Dichte und stärkerer Beschränkung eingesetzt werden (vgl. Gent und Prosser, 2000, S. 9 ff.).



Fußnoten

...5.50
Entsprechend dem eingesetzten AC-Algorithmus werden MAC-Algorithmen z.B. mit MAC-3, MAC-4 etc. benannt. Sie sind moderne Varianten des DEEB-Algorithmus (Domain Element Elimination with Backtracking) von Gaschnig (1979) zit. nach Dechter und Meiri, 1994, S. 237; Dechter und Frost, 1998, S. 45 f.; Gent und Prosser, 2000, S. 3; Grant und Smith, 1995, S. 2; Prosser, 1995b, S. 3 u. 4 bzw. dessen Vorgänger, dem Algorithmus CS2 von Gaschnig (1974) zit. nach Grant und Smith, 1995, S. 2; Prosser, 1995b, S. 3; Sabin und Freuder, 1994a, S. 12; Sabin und Freuder, 1994b, S. 126.
...5.51
In den ursprünglichen von Haralick und Elliot (1980) vorgestellten Algorithmen wird allerdings im Gegensatz zum MAC-Algorithmus nur eine schwächere Form von AC bzw. DAC erreicht, bedingt dadurch, dass keine eigentliche Propagation im Sinne eines Kantenkonsistenz-Algorithmus vorgenommen wird (vgl. Tsang, 1998, S. 355 f.).
...5.52
Für sehr einfache, unterbestimmte Probleme, die eine große Anzahl Lösungen aufweisen (engl. under-constrained problems), zahlt sich das Preprozessing durch look-ahead-Mechanismen u.U. nicht aus. Wenn sogar das durch Forward Checking angewendete look-ahead zu zeitintensiv und der Gewinn zu gering ist, empfiehlt sich der Einsatz von Backtracking bzw. Backjumping ohne look-ahead (vgl. Frost und Dechter, 1996a, S. 13).
...5.53
Bis 1993 wurden empirische Untersuchungen lediglich auf relativ begrenzte Probleme mit bis zu 25 Variablen angewendet. Die vorherrschende Meinung war, dass ausschließlich Verfahren mit einem geringen Overhead effektiv anzuwenden sind (vgl. Dechter und Frost, 1998, S. 52).
...5.54
Jede Variable wird durch alle anderen Variablen beschränkt.
...5.55
Die empirischen Untersuchungen von Haralick und Elliot (1980) beschränken sich auf das n-Damen-Problem mit $4 \leq n \leq 10$.
...5.56
Untersuchungen lassen darauf schließen, dass für sehr umfangreiche und stark beschränkte Probleme auch pfadkonsistenz-basierte look-ahead-Verfahren effektiv eingesetzt werden können (vgl. Dechter und Frost, 2002, S. 178).

next up previous contents index
Nächste Seite: 5.2.4.7 Hybride Ansätze Aufwärts: 5.2.4 Suchverfahren Vorherige Seite: 5.2.4.5 Backtracking mit Forward   Inhalt   Index