next up previous contents index
Nächste Seite: 5.3.7 -Baum-Methode Aufwärts: 5.3.6 Box-Konsistenz Vorherige Seite: 5.3.6.1 Newton-Intervallverfahren   Inhalt   Index


5.3.6.2 Erweiterungen zur Box-Konsistenz

Wenn einzelne, punktgenaue Lösungen benötigt werden, bietet es sich an, ein übergeordnetes binäres Such- bzw. Splitting-Verfahren einzusetzen. Van Hentenryck et al. (1997,1995) stellen den Branch & Prune-Algorithmus Newton vor, mit dem alle isolierten Lösungen eines ICSPs aufgefunden werden können. Der Algorithmus kann als globales Suchverfahren charakterisiert werden, welches Box-Konsistenz als Filtermechanismus einsetzt. Nachdem die Wertebereiche durch Box-Konsistenz so weit wie möglich eingeschränkt worden sind, wird ein Branching-Mechanismus eingesetzt, um einzelne Lösungen zu isolieren. Bereiche, die keine Lösung enthalten, werden ,,abgeschnitten`` bzw. verworfen.

Eine weitere Verbesserung der Box-Konsistenz findet sich bei Puget und Van Hentenryck (1998,1996) bzw. Collavizza et al. (1998,1999). Das beschriebene Verfahren eignet sich, mit dem entsprechenden Aufwand, zum Erreichen eines höheren Konsistenzgrades, genannt Box(2)-Konsistenz bzw. Bound-Konsistenz.5.108 Hier wird das Prinzip zum Erreichen von 3B-Konsistenz auf Box-Konsistenz angewendet, d.h. es wird überprüft, ob Box-Konsistenz jeweils bzgl. der oberen und unteren Intervallgrenze für das gesamte ICSP hergestellt werden kann (vgl. Abschnitt 5.3.5.2).

Neben dem verbesserten Algorithmus HC-4 zur Herstellung von Hull-Konsistenz ohne Zerlegung in primitive Constraints (vgl. Abschnitt 5.3.5.3), wird darauf aufbauend von Benhamou et al. (1999a) ein effizienterer Algorithmus BC-4 entwickelt. BC-4 basiert auf einer Kombination von HC-4 und BC-3, wie der Newton-basierte Algorithmus zur Herstellung von Box-Konsistenz von Benhamou et al. (1999a) in Anlehnung an AC-3 genannt wird.

Unter Optimierungsaspekten ebenfalls interessant ist die Arbeit von Granvilliers et al. (1999). Das hier vorgestellte Verfahren stellt Box$_{\varphi}$-Konsistenz her (mittels BC$_{\varphi}$), ein Konsistenzgrad, der aufgrund von Beschränkungen bei der Berechnung von Näherungswerten grundsätzlich schwächer ist als Box-Konsistenz, dafür allerdings effizienter berechnet werden kann. Der eingesetzte Algorithmus BC$_{\varphi}$ ist adaptiv, d.h. er passt seine Beschränkung dynamisch an, so dass u.U. ein Konsistenzgrad erreicht werden kann, der äquivalent zur Box-Konsistenz ist.



Fußnoten

...5.108
Während Dechter und Rossi (2003); Marriott und Stuckey (1999) mit bounds consistency eine der Kantenkonsistenz angenäherte und auf die Intervallgrenzen bezogene Konsistenz benennen, die ausschließlich für finite Domänen und spezielle (global) Constraints eingesetzt wird, Vu et al. (2003c); Silaghi et al. (2001); Russel und Norvig (2002); Vu et al. (2002) unter dem Begriff bound consistency jegliche auf die Intervallgrenzen bezogene Konsistenzen unabhängig von der Domäne zusammenfassen, wird von Collavizza et al. (1998,1999) mit bound consistency eine spezielle Version der Box-Konsistenz benannt.

next up previous contents index
Nächste Seite: 5.3.7 -Baum-Methode Aufwärts: 5.3.6 Box-Konsistenz Vorherige Seite: 5.3.6.1 Newton-Intervallverfahren   Inhalt   Index