next up previous contents index
Nächste Seite: 5.2.5.2 Werteordnungsheuristiken Aufwärts: 5.2.5 Heuristiken zur Variablen- Vorherige Seite: 5.2.5 Heuristiken zur Variablen-   Inhalt   Index

5.2.5.1 Variablenordnungsheuristiken

Die Belegung von Variablen mit Werten sollte in einer Reihenfolge vorgenommen werden, so dass eine vollständige, konsistente Belegung mit möglichst wenig Backtracking hergestellt werden kann. Um zu verhindern, dass große Teile von bereits belegten Variablen aufgrund von erst spät festgestellten Inkonsistenzen wiederholt neu belegt werden müssen (trashing), ist es sinnvoll ,,kritische Variablen``, von denen viele andere Belegungen abhängig sind, zu Beginn einer Suche zu belegen. Anstatt uninformiert eine Variable nach der anderen zu belegen, werden Heuristiken eingesetzt, um basierend auf der Anzahl der Elemente in den Wertebereichen und den involvierten Constraints festzustellen, wie kritisch eine Variable im Vergleich zu anderen ist (engl. most constrained first). Aufgrund dieser Heuristiken wird eine Belegungsreihenfolge generiert. Der Vorgang kann sowohl statisch, als Preprozessing vor Beginn einer Suche (engl. static variable ordering, SVO), als auch dynamisch, während einer Suche, jeweils bevor eine neue Variablenbelegung durchgeführt wird, erfolgen (engl. dynamic variable ordering, DVO). Im Gegensatz zu statischen Variablenordnungen variiert bei dynamischen die Belegungsreihenfolge der Variablen in unterschiedlichen Zweigen des Suchbaums (vgl. Ruttkay, 1998; Barták, 2003).

Da die anfangs generierte Ordnung bei Anwendung von statischen Heuristiken während der gesamten Suche beibehalten wird, ist der Berechnungsaufwand i.A. geringer, als die Anwendung von dynamischen Ordnungsheuristiken. Zudem ist die Anwendung von DVOs nicht in jedem Fall sinnvoll. So ergeben sich z.B. während der Suche mit einem einfachen, chronologischen Backtracking-Algorithmus keine zusätzlich nutzbaren Informationen. Das Constraint-Netz bzw. die Wertebereiche der Constraint-Variablen werden in diesem Fall keinerlei Änderungen unterworfen, die die Reihenfolge einer initialen Variablenordnung beeinflussen würden (vgl. Barták, 2003). Anders verhält es sich bei der Anwendung von FC und anderen look-ahead-Suchverfahren. Durch die Reduzierung der Wertebereiche der Variablen können sich Änderungen ergeben, deren Ausnutzung durch eine DVO zu einer deutlichen Verbesserung der Effizienz des Suchverfahrens führt. Im Folgenden werden die geläufigsten Variablenordnungsheuristiken vorgestellt:

fail first (FF):

Das von Haralick und Elliot (1980, S. 301 ff.) vorgestellte fail-first-Prinzip geht zurück auf eine bereits von Bitner und Reingold (1975) vorgeschlagene search rearrangement-Methode zur Optimierung von Backtracking-Algorithmen. FF wird häufig mit großem Erfolg eingesetzt5.61 und ist außer unter der Bezeichnung search rearrangement (vgl. Purdom, 1983; Kumar, 1992; Bitner und Reingold, 1975) auch unter den Namen minimum remaining values (MRV) (vgl. Bacchus und van Run, 1995; Russel und Norvig, 2002; Bacchus und Grove, 1995), minimum domain (dom) (vgl. Bessière und Régin, 1996; Chen und van Beek, 2001), dynamic search rearrangement (DSR) (vgl. Dechter und Meiri, 1994; Güsgen, 2000) und unter der allgemeinen Bezeichnung DVO (vgl. Frost und Dechter, 1994) bekannt. Die Heuristik erstellt eine Belegungsreihenfolge aufgrund des Prinzips, dass Bereiche des Suchbaums, in denen ein Fehlschlagen wahrscheinlicher ist als in anderen, zuerst durchsucht werden sollten.5.62 Auf diese Weise soll sichergestellt werden, dass Fehlschläge in einer möglichst frühen Phase der Suche erkannt werden.5.63 Infolgedessen wird bei Anwendung der FF-Heuristik versucht, von den verbleibenden Variablen immer diejenige mit dem kleinsten Wertebereich als nächstes mit einem konsistenten Wert zu belegen. Trotz seiner Einfachheit ist FF damit sehr effektiv, denn durch die (aufgrund der geringeren Anzahl zu testender Werte) verminderte Verzweigungstiefe im Suchbaum, ist die Wahrscheinlichkeit tatsächlich höher, mögliche Inkonsistenzen früher festzustellen (vgl. Haralick und Elliot, 1980, S. 308). In Kombination mit einfachem BT kann die FF-Heuristik statisch eingesetzt werden, d.h. es wird vor Beginn der Suche eine fixe Variablenordnung aufsteigend bzgl. der Wertebereiche generiert. Zusammen mit look-ahead-Suchalgorithmen, während deren Ausführung inkonsistente Werte aus den Domänen von noch unbelegten Variablen entfernt werden, wird FF dynamisch angewendet.

minimal width ordering (MWO):

Die von Freuder (1982, S. 27 ff.) beschriebene minimal-width-ordering-Heuristik wird auch kurz mit min-width (vgl. Frost und Dechter, 1994) und minw (vgl. Bessière und Régin, 1996) benannt. Mit ihrer Hilfe wird versucht, eine Reduzierung des Backtracking vorzunehmen, indem Variablen, die mehr beschränkt werden als andere, in der Reihenfolge der zu belegenden Variablen weiter vorne angeordnet werden. Umgekehrt sollten Variablen, die auf weniger andere Variablen angewiesen sind, später mit einem Wert belegt werden, da für diese Variablen einfacher eine gültige Belegung gefunden werden kann. Die MWO-Heuristik wertet zur Generierung der Reihenfolge allerdings nicht wie FF die Größe der Wertebereiche aus, sondern die Beschränkung der Variablen durch die Constraints. Dazu wird eine Ordnung mit einer möglichst geringen ,,Weite`` (engl. width) erzeugt. Die Weite einer Variable ergibt sich dabei aus der Anzahl der Variablen, die sich in einer gegebenen totalen Ordnung vor dieser Variable befinden und im Constraint-Graphen benachbart sind.5.64 Die Weite einer Ordnung ist die maximale Weite aller Variablen unter dieser Ordnung, und die Weite eines Constraint-Netzes ist die minimale Weite aller möglichen Ordnungen.

Beispiel 5.2.7   In Abbildung 5.18 ist dazu ein Beispiel aufgeführt. Für den in 5.18(a) dargestellten Constraint-Graphen ist in 5.18(b) eine Variablenordnung der Weite 2 angeben (maximale Weite der beteiligten Variablen). Dies ist in diesem Fall zugleich die minimale Ordnung des Constraint-Graphen.

Abbildung 5.18: Die Weite einer Variablenordnung (vgl. Freuder, 1982, S. 29)
\begin{figure}\centering
\includegraphics[width=14.5cm]{images/constraints_width}
\ifx\pdfoutput\undefined
\fi
\end{figure}

Wenn es gelingt, diese Ordnung mit minimaler Weite zu finden, ist sichergestellt, dass sich Variablen, auf die viele andere Variablen durch Constraint-Verbindungen angewiesen sind, weiter vorne in der Ordnung befinden, wodurch wiederum die Notwendigkeit von Backtracking verringert wird.5.65 Die MWO-Heuristik ist eine statische Heuristik, die vor Beginn einer Suche ausgeführt wird.

maximum cardinality ordering (MCO):

Das maximum-cardinality-ordering kann als eine Approximation an die Ergebnisse der MWO-Heuristik angesehen werden (vgl. Tsang, 1993, S. 179 ff.). Die MCO-Heuristik wird auch unter der Bezeichnung CARD (vgl. Dechter und Meiri, 1994) bzw. card (vgl. Bessière und Régin, 1996) geführt. MCO ist ebenfalls eine statische Variablenordnungsheuristik und hat ebenso wie MWO das Ziel, Backtracking dadurch zu reduzieren, dass Variablen mit vielen Abhängigkeiten möglichst früh mit Werten belegt werden. Die Ordnung wird dazu in umgekehrter Reihenfolge erstellt. Begonnen wird mit einer beliebigen Variable, die das letzte Element in der Belegungsreihenfolge darstellt. Danach wird der Reihe nach jeweils die Variable ausgewählt, die mit den meisten bisher ausgewählten Variablen über ein Constraint verbunden ist. Die Weite einer mit der MCO-Heuristik generierten Ordnung ist häufig größer als die einer durch die MWO-Heuristik generierten minimalen Ordnung, kann dafür aber mit weniger Aufwand hergestellt werden.

maximum degree ordering (MDO):

Eine der MWO ebenfalls ähnliche aber wesentlich simplere Methode ist die maximum-degree-ordering-Heuristik (vgl. Tsang, 1993, S. 166), auch kurz DEG (vgl. Dechter und Meiri, 1994) bzw. deg (vgl. Bessière und Régin, 1996; Chen und van Beek, 2001) genannt. Das Vorgehen besteht darin, die Variablen einfach absteigend nach ihrer Stelligkeit bzw. dem Grad ihres Vorkommens in den Constraints anzuordnen. Das heißt Variablen, die von vielen Constraints beschränkt werden, befinden sich vorn in der Belegungsreihenfolge. Die MDO-Heuristik ist ebenfalls eine statische Ordnungsheuristik, approximiert bei deutlich geringerem Berechnungsaufwand MWO und verringert das Backtracking während des Suchvorgangs.

minimal bandwidth ordering (MBO):

Im Gegensatz zu den bereits angesprochenen Heuristiken ist die minimal-bandwidth-ordering-Heuristik (vgl. Tsang, 1993, S. 166 ff.) nicht dadurch motiviert, die Notwendigkeit von Backtracking zu verringern, sondern die Abstände zwischen sich gegenseitig beschränkenden Variablen innerhalb der Ordnung (Minimierung der ,,Bandbreite``). Durch die in der Ordnung möglichst dichte Platzierung von im Constraint-Netz benachbarter Variablen ist gewährleistet, dass im Konfliktfall ein chronologischer Backtracking-Algorithmus kürzere Strecken im Suchbaum überwinden muss, und dadurch möglichst schnell auf die konfliktauslösende Variable trifft. Je kleiner die Bandbreite einer Ordnung ist, umso eher kann an die Stellen zurückgegangen werden, die auslösend für Backtracking sind. Während sich die Bandbreite einer Variablen aus dem maximalen Abstand zu seinen Nachbarn bzgl. des Constraint-Netzes innerhalb einer Ordnung ergibt, ist die Bandbreite einer Ordnung die maximale Bandbreite aller existierender Variablen, und die Bandbreite eines Constraint-Netzes wiederum die minimale Bandbreite aller möglichen Ordnungen. Die MBO-Heuristik ist eine statische Ordnungsheuristik, die, als Preprozessing vor Beginn einer Suche, eine totale Ordnung mit minimaler Bandbreite erzeugt.

Die Anwendung von Ordnungsheuristiken geschieht in Abhängigkeit von der Problemstellung und von dem eingesetzten Lösungsverfahren. MWO, MCO, MDO und MBO sind statische Variablenordnungsheuristiken, die eine Ordnung generieren, bevor der Suchvorgang gestartet wird. Sie nutzen die Struktur des Constraint-Graphen, berücksichtigen jedoch nicht die Veränderungen der Wertebereiche während der Suche durch ein look-ahead-Suchverfahren. Die FF-Heuristik hingegen kann statisch und dynamisch eingesetzt werden und berücksichtigt die Domänen der Constraint-Variablen, nicht jedoch die Topologie des Constraint-Graphen.

Die Effizienz der Heuristiken ist problemabhängig. Während FF umso erfolgreicher ist, je signifikanter die Größe der Wertebereiche schwankt bzw. wenn ein Konsistenzverfahren als look-ahead zum Einsatz kommt,5.66 sind MWO, MCO und MDO effizient anwendbar für Probleme, in denen einige Variablen von mehr Constraints beschränkt werden als andere. Im Umkehrschluss sind diese Ordnungsheuristiken nicht sinnvoll einsetzbar, wenn alle Wertebereiche dieselbe Größe aufweisen und kein Konsistenzverfahren eingesetzt wird (FF) bzw. wenn der Constraint-Graph einen einheitlichen Grad oder gar vollständige Vernetzung aufweist (MWO, MCO und MDO). Die MBO-Heuristik ist ausschließlich zur Optimierung von Suchverfahren mit chronologischem Backtracking geeignet. Ein hoher Vernetzungsgrad im Constraint-Netz wirkt sich hier negativ auf das Ergebnis aus, da das Maximum der Vernetzung die minimale Bandbreite des Constraint-Netzes diktiert (vgl. Tsang, 1993, S. 182).5.67 In der Vergangenheit hat sich häufig die Überlegenheit von dynamischen gegenüber statischen Variablenordnungsheuristiken gezeigt vgl. Bacchus und van Run, 1995, S. 272; Dechter und Meiri, 1994, S. 236; Frost und Dechter, 1994, S. 304; Purdom, 1983, S. 132. Viele Arbeiten zu diesem Thema kommen zu dem Schluss, dass die Anwendung speziell des FF-Prinzips für viele Anwendungen eine sehr günstige Heuristik ist, die sich insbesondere in Kombination mit FC und FC-CBJ als sehr effizient erwiesen hat vgl. Bacchus und van Run, 1995, S. 270; Bacchus und Grove, 1995, S. 308.

Die genannten Heuristiken können zur Effizienzsteigerung miteinander kombiniert werden. Da es für ein Constraint-Netz für gewöhnlich jeweils mehrere Ordnungen gibt, die minimale Weite und minimale Bandbreite aufweisen, ist es z.T. möglich, eine Ordnung zu generieren, die gleichzeitig MWO und MBO aufweist, d.h. beide Minima miteinander vereint. Für Constraint-Netze, in denen dies nicht möglich ist, kann eine Annäherung erreicht werden. Die Kombination von MWO oder MBO mit FF kann auf mehrere Arten erfolgen:

  1. Die Auswahl der Variablen erfolgt in erster Linie nach der MWO- bzw. MBO-Heuristik. Bei Konflikten, d.h. wenn mehrere Variablen denselben Vernetzungsgrad besitzen, wird gemäß FF aus diesen die Variable mit dem kleineren Wertebereich ausgewählt (vgl. Tsang, 1993, S. 184).

  2. Umgekehrt kann die Anwendung des FF-Prinzips im Vordergrund stehen, d.h. die Auswahl erfolgt nach Größe der Wertebereiche. Existieren mehrere Variablen, deren Wertebereiche dieselbe Anzahl Elemente aufweisen, wird aus diesen mittels MWO oder MBO die nächste zu belegende Variable ausgewählt (vgl. Tsang, 1993, S. 182 ff.). Als sehr effektiv hat sich die Kombination von FF mit der an MWO angenäherten und weniger rechenintensiven MDO-Heuristik erwiesen (vgl. Frost und Dechter, 1995, S. 573). Der resultierende Algorithmus wird von Bessière und Régin (1996) auch FC-CBJ-dom+deg genannt. Anstatt wie FC-CBJ-dom in Fällen, in denen die Wertebereiche von Variablen dieselbe Anzahl Elemente aufweisen, die nächste Variable zufällig auszuwählen, berücksichtigt dieser Algorithmus als nächstes die Variable mit dem höheren Vernetzungsgrad im Constraint-Netz.

  3. Bei beiden erstgenannten Kombinationsmöglichkeiten steht jeweils eine Heuristik besonders im Vordergrund. Während sich jedoch die FF-Heuristik in CSPs mit geringer Constraint-Dichte weniger gut hinsichtlich der Vermeidung von Backtracking verhält, ist der Einsatz von MDO dort im Vergleich günstiger. Dafür wird MDO umso ungünstiger, je mehr Constraints berücksichtigt werden müssen. Die Heuristiken verhalten sich also invers zueinander, was in den genannten Kombinationen aufgrund der Dominanz jeweils einer Heuristik nicht vollständig ausgeglichen werden kann. Eine Kombination von FF und MDO, die beide Vorteile verbindet und die Nachteile weitestgehend kompensiert, wird von Bessière und Régin (1996, S. 69 ff.) vorgestellt: dom/deg. Nach dieser Heuristik wird jeweils die Variable als nächstes mit einem Wert belegt, deren Verhältnis von Größe des Wertebereichs zu Vernetzungsgrad am geringsten ist. Die Heuristik wird von Bessière und Régin (1996) zur Optimierung des MAC-Algorithmus eingesetzt, wobei MAC-dom/deg eine gleich bleibende Verbesserung hinsichtlich der Vermeidung von Backtracking, bezogen auf die Constraint-Dichte, erreicht und demnach insgesamt der MAC-dom+deg-Variante überlegen ist. Selbiges gilt, wenn auch weniger stark ausgeprägt, für FC-CBJ-dom/deg.

Ob sich der betriebene Aufwand zur Herstellung einer Variablenordnung lohnt, ist allerdings problem- bzw. domänenabhängig und muss von Fall zu Fall entschieden werden. Da es sich bei den oben genannten um allgemeine Heuristiken handelt, kann es u.U. domänenspezifische Heuristiken geben, die eine wesentlich effizientere Problemlösung ermöglichen.



Fußnoten

...5.61
Beispielsweise in in der CLP-Sprache CHIP (vgl. Tsang, 1993, S. 178 u. 188).
...5.62
,,To succeed, try first where you are most likely to fail`` (Haralick und Elliot, 1980, S. 263).
...5.63
Ähnlich dem FC, PLA, FLA und anderen look-ahead-Verfahren, die ebenfalls dem frühzeitigen Auffinden von inkonsistenten Wertebelegungen dienen.
...5.64
Das heißt es existiert ein Constraint zwischen diesen beiden Variablen.
...5.65
Freuder (1982, S. 27) weist zudem nach, dass, für ein CSP mit einem strengen Konsistenzgrad $>$ der Weite, eine Lösung gänzlich ohne Backtracking gefunden werden kann - vorausgesetzt die Variablen werden in der entsprechenden Reihenfolge mit Werten belegt. Dies wirkt sich z.B. bei der Behandlung von baumartigen Constraint-Graphen (Weite = 1 für jede beliebige Belegungsreihenfolge) mittels AC bzw. DAC aus (vgl. Abschnitt 5.2.3.5).
...5.66
Viele stark beschränkende Constraints wirken sich vorteilhaft bzgl. starker Schwankungen bei Anwendung von look-ahead-Verfahren aus und damit entsprechend für die Anwendung der FF-Heuristik.
...5.67
Je mehr Variablen bzw. Constraints Einfluss auf die Konsistenz der Belegung einer Variable haben, umso mehr Fehlerquellen müssen im Konfliktfall durch Backtracking angesteuert werden, d.h. umso größer wird der Abstand voneinander abhängiger Variablen innerhalb der Ordnung und damit die minimale Bandbreite.

next up previous contents index
Nächste Seite: 5.2.5.2 Werteordnungsheuristiken Aufwärts: 5.2.5 Heuristiken zur Variablen- Vorherige Seite: 5.2.5 Heuristiken zur Variablen-   Inhalt   Index