8.3.1 Übersicht über die Problemstellungen

Für das Programm YacsTester werden die Constraint-Lösungsstrategien aus Anhang C ff. genutzt. Für jede dort enthaltene Strategie existiert in YacsTester eine Methode, die ein Testproblem generiert und an den Constraint-Manager von YACS überträgt:

• In der Methode NCSolverTest (Zeile 114-160) wird die Strategie mit dem Namen low_consistency genutzt, um Knotenkonsistenz durch NCSolver herzustellen. Das in der Methode generierte Problem ist eine Erweiterung eines Beispielproblems von Marriott und Stuckey (1999, S. 95).

• Durch die Methode AC3SolverTest (Zeile 166-224) wird die Strategie medium_consistency eingesetzt, um durch die Kombination von NCSolver und AC3Solver für ein Kartenfärbeproblem einer Australienkarte strenge 2-Konsistenz herzustellen vgl. Marriott und Stuckey, 1999, S. 86 u. 89; Russel und Norvig, 2002, S. 138.^8.3

• SingleSolutionBTSolverTest (Zeile 230-280) nutzt die Strategie simple_search um eine einfache Backtracking-Suche auf ein Constraint-Beispiel von Marriott und Stuckey (1999, S. 89 u. 91) anzuwenden. Der in der Strategie spezifizierte SingleSolutionBTSolver gibt die erste Lösung zurück auf die er stößt, oder meldet entsprechend eine Inkonsistenz.

• Die BacktrackingSolverTest (Zeile 286-336) verwendet den in der Strategie search spezifizierten BacktrackingSolver, um sämtliche Lösungen für das Smuggler's-Knapsack-Problem zu generieren (vgl. Marriott und Stuckey, 1999, S. 101).^8.4

• Die in der Methode MAC3SolverTest (Zeile 342-392) genutzte Strategie mit dem Namen search_with_look-ahead versucht ebenfalls das Smuggler's-Knapsack-Problem zu lösen (vgl. Marriott und Stuckey, 1999, S. 101), setzt dafür allerdings den MAC3Solver ein.

• In der Methode HullConsistencySolverTest (Zeile 398-439) wird der in der Strategie interval_consistency spezifizierte HullConsistencySolver eingesetzt, um das Constraint-Problem aus Beispiel 5.3.5 zu propagieren (vgl. Davis, 1987, S. 286 f.). Weil HullConsistencySolver derzeit ausschließlich Gleichungen unterstützt, wurde das Problem entsprechend modifiziert. Außerdem müssen diesem Constraint-Solver die impliziten Funktionen eines Constraints (solution functions, vgl. Abschnitt 5.3.4.1) vorgefertigt übergeben werden (Zeile 409-410).

Um Redundanzen zu vermeiden, wurden nicht alle implementierten Constraint-Solver in das Testprogramm YacsTester aufgenommen. Die Ergebnisse von AC3Solver und MAC3Solver unterscheiden sich nicht von den Ergebnissen von ACSolver und MACSolver, daher wurde auf die Darstellung letzterer an dieser Stelle verzichtet.

Fußnoten

...^8.3

Die Bundesstaaten einer Australienkarte (WA, NT, SA, Q, NSW, V, T) sind derart mit den Farben ,,rot``, ,,grün`` und ,,blau`` zu markieren, dass benachbarte Staaten in jedem Fall unterschiedliche Farben aufweisen.

...^8.4

Smuggler's Knapsack: Ein Schmuggler hat einen Rucksack mit einer begrenzten Aufnahmefähigkeit von insgesamt 9 Wareneinheiten. Er kann während einer Schmuggeltour 4 Einheiten Whisky (W), 3 Einheiten Parfüm (P) und 2 Einheiten Zigaretten (C) schmuggeln. Der Profit für das Schmuggeln einer Einheit Whisky liegt bei 15$, der Profit für Parfüm und Zigaretten entsprechend bei 10$ und 7$. Was kann der Schmuggler in seinem Rucksack mitnehmen, wenn er min. 30$ Profit voraussetzt?