next up previous contents index
Nächste Seite: 7.7.4 Beispiel für einen Aufwärts: 7.7 Constraint-Lösungsstrategien Vorherige Seite: 7.7.2 Einbettung in Constraint-Netze   Inhalt   Index

7.7.3 Ausführungskontrolle

Zur Auswertung der Constraints, d.h. zur Anwendung der Constraint-Lösungsstrategien, dient die Methode evaluate() des YCM (siehe Abbildung 7.2). Der Constraint-Manager verwaltet intern eine Liste mit den existierenden Constraint-Netzen, welche sich über den Namen der jeweils zugehörigen Strategie referenzieren lassen. Zur Anwendung der Constraint-Lösungsstrategien werden innerhalb von evaluate() für jede Phase des Lösungsprozesses sämtliche Constraint-Netze der Reihe nach durchgegangen, und die der Phase entsprechende Methode des Constraint-Netzes zur Anwendung der spezifizierten Constraint-Solver aufgerufen: Die Anwendung der Preprozessing-Solver geschieht durch den Aufruf der Methode triggerPreprocessing() der Klasse ConstraintNet (siehe Abbildung 7.7). Konsistenz wird durch den Aufruf der Methode triggerConsistency() in derselben Klasse hergestellt. Die Lösungssuche wird entsprechend mit triggerSearch() gestartet.

Die Methode triggerSearch() unterscheidet sich von triggerPreprocessing() und triggerConsistency() dadurch, dass zu Beginn von triggerSearch() ggf. existierende Lösungen der Constraint-Netze entfernt werden. Da zwischen mehreren Aufrufen der Methode evaluate() sowohl die Constraint-Netze als auch die Wertebereiche von Constraint-Variablen modifiziert werden können, wird auf diese Weise sichergestellt, dass keine potentiell inkonsistenten Lösungen für ein Teilproblem vorgehalten werden.

Der Ablauf der Methode evaluate() des Constraint-Managers ist in dem Aktivitätsdiagramm in Abbildung 7.8 dargestellt. Der Aufruf der jeweiligen trigger-Methoden erfolgt in jeder Phase solange, bis von den entsprechenden Constraint-Solvern keine Einschränkungen der Wertebereiche mehr gemeldet werden, dargestellt durch das Flag domainModification. Die wiederholten Iterationen sind notwendig, damit Wertebereichseinschränkungen innerhalb eines Constraint-Netzes von den übrigen Constraint-Netzen berücksichtigt werden können.7.13 Durch diese ,,Metapropagation`` profitieren die vorhandenen Constraint-Netze von den Wertebereichseinschränkungen untereinander und erreichen insgesamt eine erhöhte Filterrate inkonsistenter Werte.

Abbildung 7.8: Schematische Darstellung des Constraint-Lösungsvorgangs von YACS
\begin{figure}\centering
\includegraphics[scale=0.7]{images/implementierung_kontrolle}
\ifx\pdfoutput\undefined
\fi
\end{figure}

An dieser Stelle wird deutlich, dass die Unterscheidung des Lösungsprozesses in unterschiedliche Phasen semantisch einen Unterschied macht, wenn auch syntaktisch keine Unterscheidung feststellbar ist (die Schnittstellen für die Constraint-Solver sind identisch). Bei Überlappungen von Constraint-Netzen haben Wertebereichseinschränkungen Einfluss auf benachbarte Constraint-Netze, allerdings ausschließlich innerhalb einer Phase des Lösungsprozesses. Es macht daher Sinn, z.B. einen Algorithmus zur Konsistenzherstellung auch wirklich als ,,ausgewiesenen`` Konsistenz-Solver innerhalb von YACS zu nutzen (durch Spezialisierung der entsprechenden abstrakten Oberklasse und dem entsprechenden Eintrag innerhalb einer Constraint-Lösungsstrategie), da er ansonsten nicht von den Wertebereichseinschränkungen anderer Konsistenz-Solver profitiert und umgekehrt.

Nicht unbedingt offensichtlich ist, warum auch die Constraint-Solver während der Phase der Lösungssuche eine Änderung der Wertebereiche anzeigen können. In der Tat liefern alle derzeit implementierten Suchalgorithmen an dieser Stelle ausschließlich false zurück. Zum einen besteht aus Gründen einer einheitlichen Schnittstelle auch hier die Möglichkeit der Änderungsanzeige, zum anderen wird dadurch die Möglichkeit gegeben, dass Suchalgorithmen ggf. Wertebereichseinschränkungen vornehmen (z.B. durch eine Algorithmus-interne, vorgeschaltete Konsistenzherstellung). Andere Suchalgorithmen können auf diesem Weg davon Kenntnis erlangen, dass es (weitere) inkonsistente Werte gibt, die nicht Teil einer (globalen) Lösung sein können.7.14

Um auch phasenübergreifend Wertebereichseinschränkungen propagieren zu können, wäre eine weitere, äußere Iteration des Kontrollalgorithmus aus Abbildung 7.8 notwendig. In Bezug auf eine globale, Constraint-Netz übergreifende Lösungssuche wäre es denkbar, dass Suchalgorithmen, die für einzelne Constraint-Netze (Teilprobleme) lokal konsistente Lösungen generiert haben, aus diesen Lösungen konsistente Wertebereiche für die involvierten Constraint-Variablen ableiten. In Bezug auf das jeweilige Teilproblem sind diese Wertebereiche ,,global`` konsistent (vollständige Suchverfahren vorausgesetzt), und würden bei einer erneuten, äußeren Iteration eines erweiterten Kontrollalgorithmus ggf. weitere Wertebereichseinschränkungen durch die jeweilige Metapropagation der anderen Phasen erreichen.7.15

So gesehen ist die derzeitige Implementierung des Kontrollalgorithmus des YACS-Frameworks eine Vorstufe für die Lösungssuche im globalen Kontext. Wohlgemerkt betrifft dies ausschließlich die globale Propagation, denn nach dem oben beschriebenen Schema lassen sich immer noch ausschließlich lokale Lösungen generieren (auch wenn bereits global propagiert wird). Eine globale, Constraint-Netz übergreifende Lösungssuche macht eine übergeordnete Suche innerhalb eines Meta-Constraint-Solvers notwendig, wie er in Abschnitt 6.4.3 ff. beschrieben wurde. Einen solchen bietet die derzeitige Realisierung von YACS nicht. Aus Effizienzgründen wurde daher auf eine weitere, äußere Iteration bisher verzichtet, und der Kontrollalgorithmus stattdessen in seiner jetzigen Form belassen.



Fußnoten

...7.13
Aufgrund des vorhandenen globalen Namensraums für Constraint-Variablen (vgl. Abschnitt 7.5).
...7.14
In diesem Fall kann allerdings für ein Teilproblem, für das in einem vorherigen Schritt einer Lösungsstrategie ein bestimmter Konsistenzgrad hergestellt wurde, und das Überlappungen mit einem Teilproblem aufweist, auf welches eine derartige Lösungssuche angewendet wurde, nach Anwendung der Suche dieser Konsistenzgrad nicht mehr garantiert werden.
...7.15
Zum Beispiel durch eine Strategie, die keinen Constraint-Solver zur Lösungssuche enthält, allerdings Überlappungen mit Variablen eines Constraint-Netzes aufweist, deren Strategie eine Suche vorsieht. So wie die Variablen des Constraint-Netzes dieser Strategie ggf. weitere Wertebereichseinschränkungen erfahren, haben hier definierte Constraints ggf. Auswirkungen auf Constraint-Netze mit (globaler) Lösungssuche.

next up previous contents index
Nächste Seite: 7.7.4 Beispiel für einen Aufwärts: 7.7 Constraint-Lösungsstrategien Vorherige Seite: 7.7.2 Einbettung in Constraint-Netze   Inhalt   Index