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:
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.
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.
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.
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.
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.
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:
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.