7.6 Implementierte Constraint-Lösungsverfahren

In der Abbildung 7.6 ist eine Übersicht über die Klassenhierarchie des Unterpackages yacs.solver und der implementierten Constraint-Lösungsverfahren zu sehen. Sämtliche Constraint-Solver müssen das Interface Solver implementieren, in der die Methode evaluate() definiert wird. Je nachdem, ob ein Solver für das Preprozessing, für die Konsistenzherstellung oder die Lösungssuche eingesetzt werden soll, muss die entsprechende, abstrakte Oberklasse spezialisiert werden: PreprocessingSolver, ConsistencySolver oder SearchSolver. Während die evaluate()-Methode von den abstrakten Solver-Oberklassen implementiert wird, deklariert jede Oberklasse, wiederum in Abhängigkeit von der entsprechenden Lösungsphase, eine abstrakte Methode, die von evaluate() aufgerufen wird und jeweils von den konkreten Constraint-Solvern implementiert werden muss: process(), propagate() und search(). Die derart gekapselten Lösungsalgorithmen realisieren ein Entwurfsmuster, das ,,Strategie`` (engl. strategy) genannt wird (vgl. Gamma et al., 1996, S. 373 ff.). Auf diese Weise wird sichergestellt, dass der Constraint-Lösungsvorgang unabhängig von den tatsächlich zum Einsatz kommenden Lösungsalgorithmen durchgeführt werden kann. Die abstrakten Solver-Klassen bzw. das Solver-Interface sind Teil des Framework-Layers von YACS, die konkreten Implementierungen der Algorithmen sind entsprechend dem Algorithmus-Layer zugehörig (vgl. Abschnitt 6.5).

Abbildung 7.6: Übersicht über die implementierten Constraint-Lösungsverfahren

Im Fokus der Umsetzung dieser Arbeit steht weniger die Implementierung von möglichst effizienten Verfahren zum Lösen von Constraint-Problemen, als vielmehr die flexiblen und dynamischen Aspekte innerhalb eines modularen Constraint-Frameworks. Entsprechend wurden an dieser Stelle lediglich eine Reihe einfacher Constraint-Lösungsverfahren realisiert, an denen die Funktionalität von YACS demonstriert werden kann. So wurde für Constraints mit finiten Domänen neben einfacher Knotenkonsistenz in der Klasse NCSolver bisher lediglich Kantenkonsistenz realisiert: ACSolver und AC3Solver (die letztere Klasse implementiert den AC-3-Algorithmus aus Abbildung 5.6). Als Suchverfahren für FD-Constraints wurden zwei Backtracking-Suchalgorithmen implementiert: SingleSolutionBTSolver und BacktrackingSolver (für letztere Klasse siehe den Algorithmus in Abbildung 5.15). Der BacktrackingSolver wurde mit vorhandenen Algorithmen für Knoten- und Kantenkonsistenz zu zwei MAC-Varianten um look-ahead-Mechanismen erweitert: MACSolver und MAC3Solver. Sowohl BacktrackSolver als auch die darauf basierenden MACSolver und MAC3Solver generieren über eine Hilfsklasse zu Beginn des Suchvorgangs eine statische Variablenordnung nach der dom/deg-Heuristik (vgl. Abschnitt 5.2.5). Diese Heuristik ist eine Kombination des fail-first-Prinzips mit der maximum-degree-ordering-Heuristik, welche sich i.A. als recht effizient erwiesen hat (vgl. Bessière und Régin, 1996, S. 69 ff.).

Spezielle Algorithmen zur Behandlung von n-ären FD-Constraints wurden bisher nicht implementiert, allerdings sind beide Backtracking-Solver in der Lage, n-stellige Constraint-Netze nach Lösungen zu durchsuchen. Die Algorithmen in NCSolver und ACSolver sind zudem ,,optimistisch`` implementiert: Constraints mit mehr als einer Variable (NCSolver) bzw. mehr als zwei Variablen (ACSolver) werden lediglich ignoriert, die anderen entsprechend auf Konsistenz überprüft und deren Domänen ggf. eingeschränkt. Die Implementierung in AC3Solver hingegen generiert eine Exception, falls das Constraint-Problem neben unären und binären auch höher-stellige Constraints aufweist. Analog gilt dies für MACSolver und MAC3Solver.

Für Intervalldomänen existiert in YACS mit der Klasse HullConsistencySolver ein Constraint-Solver, durch dessen Algorithmus Hull- bzw. 2B-Konsistenz für ein Constraint-Problem mit reellwertigen Intervalldomänen hergestellt werden kann (siehe Algorithmus in Abbildung 5.23). Die Stelligkeit der Constraints ist hierbei irrelevant, allerdings ist der Solver derzeit noch recht einfach gehalten: Eine Zerlegung von Constraints wurde nicht implementiert, so dass für die korrekte Ausführung des Solvers als Eingabe ausschließlich vorbereitete solution functions, d.h. die impliziten Funktionen eines Constraints, zulässig sind (vgl. Abschnitt 5.3.4.1). Außerdem lassen sich durch die Intervallverarbeitung von YACS zurzeit ausschließlich Wertebereiche von Intervallvariablen in Gleichungen einschränken. Constraint-Ausdrücke mit Ungleichungen werden implementierungsbedingt bisher nicht unterstützt.

Auf die Umsetzung von Preprozessing-Verfahren, wie bspw. die Transformation n-ärer in binäre (FD-)Constraints durch Einführung ,,umfassender Variablen`` (vgl. Abschnitt 5.2.6.2) oder die Zerlegung von komplexen (reellwertigen) Constraint-Ausdrücken als Vorstufe zur Herstellung von solution functions (vgl. Abschnitt 5.3.4.1) bzw. Projektionen (vgl. Definition 5.3.14), wurde verzichtet. Eine Implementierung derartiger Mechanismen würde über den Rahmen dieser Arbeit hinausgehen und ist nicht notwendig, um die Funktionalität des YACS-Frameworks zu demonstrieren.

Erwähnenswert ist, dass die FD-Solver von YACS in der Lage sind, sowohl numerische als auch symbolische Wertebereiche zu verarbeiten. Durch die Kapselung der Elemente und deren Operatoren in den Wertebereichen, spielt es keine Rolle, welche Art Werte propagiert werden (vgl. Abschnitt 7.5.3). Außerdem ist zu beachten, dass aufgrund des globalen Namensraums Variablen mit demselben Namen, die von Constraint-Solvern in unterschiedlichen Strategien verarbeitet werden, YACS-intern dasselbe Objekt darstellen. Dies kann unbeabsichtigte Seiteneffekte hervorrufen, daher sollte bei der Namensgebung von Variablen dieser Umstand entsprechende Beachtung erfahren.^7.11

Die im YACS-Framework bisher implementierten Constraint-Lösungsverfahren werden an dieser Stelle übersichtlich mit einer kurzen Beschreibung aufgeführt:

• NCSolver: Ein Constraint-Solver zum Herstellen von Knotenkonsistenz über finite Domänen nach Marriott und Stuckey (1999, S. 94).

• ACSolver: Ein Constraint-Solver zum Herstellen von Kantenkonsistenz über finite Domänen nach Marriott und Stuckey (1999, S. 94).

• AC3Solver: Ein Constraint-Solver zum Herstellen von Kantenkonsistenz über finite Domänen mittels AC-3 nach Mackworth (1977a, S. 106).

• HullConsistencySolver: Beinhaltet einen Algorithmus zum Herstellen von Hull-Konsistenz bzw. 2B-Konsistenz für Variablen mit Wertebereichen aus reellwertigen Intervallen. Der Algorithmus orientiert sich am Waltz-Filteralgorithmus und den Beschreibungen von Davis (1987), Hyvönen (1992) und Lhomme (1993). Eine Zerlegung der Constraints findet nicht statt, außerdem lassen sich ausschließlich Constraints verarbeiten, die bereits vollständig als implizite Funktionen (solution functions, vgl. Abschnitt 5.3.4.1) bzw. als ,,Projektionen`` vorliegen (vgl. Definition 5.3.14). Implementierungsbedingt lassen sich derzeit ausschließlich implizite Funktionen verarbeiten, die als Gleichungen vorliegen.

• SingleSolutionBTSolver: Ein rekursiver Backtracking-Solver für finite Domänen in Anlehnung an Marriott und Stuckey (1999, S. 90). In dieser Implementierung allerdings wird nicht nur true/false zurückgegeben, sondern ggf. eine Lösung generiert. Dies ist die erste Lösung, die durch den Suchalgorithmus aufgefunden wird. Der Solver eignet sich in erster Linie für die Überprüfung, ob ein Problem inkonsistent ist oder nicht.

• BacktrackingSolver: Ein Backtracking-Solver zur Lösungssuche in einem Constraint-Problem mit finiten Domänen nach Dechter und Frost (1998, S. 13) bzw. Dechter und Frost (2002, S. 152). Der Solver wurde dahingehend modifiziert, dass anstatt lediglich einer Lösung alle möglichen Lösungen eines Problems gefunden werden.

• MACSolver: Ein MAC-Solver zur Lösungssuche mit look-ahead in einem Constraint-Problem mit finiten Domänen nach Dechter und Frost (2002, S. 175 u. 178). Der Solver ist eine Erweiterung des BacktrackingSolver. Als look-ahead-Mechanismus wird ACSolver eingesetzt. Ebenso wie BacktrackingSolver ist MACSolver in der Lage, anstatt lediglich einer Lösung alle Lösungen eines Problems zu generieren.

• MAC3Solver: Ein MAC-3-Solver zur Lösungssuche mit look-ahead in einem Constraint-Problem mit finiten Domänen nach Dechter und Frost (2002, S. 175 u. 178). Der Solver ist ebenfalls eine Erweiterung von BacktrackingSolver. In diesem Fall kommt AC3Solver als look-ahead-Mechanismus zum Einsatz. Auch MAC3Solver ist als vollständiger Solver implementiert, d.h. er ist ebenso wie BacktrackingSolver in der Lage, sämtliche Lösungen eines Problems zu finden.

Wie aus dem UML-Diagramm in Abbildung 7.6 hervorgeht, nutzen die beiden MAC-Suchalgorithmen die vorhandenen Konsistenz-Solver für das erforderliche look-ahead direkt, indem sie die benötigten Klassen aggregieren. Zur Laufzeit werden den instantiierten Konsistenz-Solvern in der look-ahead-Phase die jeweils einzuschränkenden Constraints übergeben und die Propagierung gestartet. Je nach Problemstellung und Härte des Problems, kann der Aufwand für das durchgeführte look-ahead potentiell unnötiger Overhead sein (vgl. Abschnitt 4.3 und Abschnitt 5.2.4.6). Generell ist für Probleme mit vielen Lösungen und wenig Filtermöglichkeiten das einfache Backtracking den MAC-Algorithmen vorzuziehen.

Fußnoten

...^7.11

Für die Behandlung von umfangreichen Problemstellungen, für die eine separate Verarbeitung in voneinander getrennten Constraint-Netzen sichergestellt werden soll, würde sich die Verwendung von Präfixen für die Namen von Constraint-Variablen anbieten. Ein Präfix könnte bspw. der Name oder ein Kürzel für die jeweilige Constraint-Lösungsstrategie sein.