next up previous contents index
Nächste Seite: 5.3.3 Label Inference Aufwärts: 5.3 Intervall Constraint Satisfaction Vorherige Seite: 5.3.1.4 Konvexität und Diskontinuität   Inhalt   Index

5.3.2 Intervall-Splitting

Die vorgestellten intervallmathematischen bzw. -arithmetischen Grundlagen sind Basis der Constraint-Lösungsalgorithmen, die Intervall-Constraints verarbeiten und insbesondere dazu dienen, Intervallgrenzen einzuschränken bzw. Lösungen zu bestimmen. John G. Cleary stellte das Konzept des domain splitting bzw. interval splitting vor, einem Suchverfahren zur Bestimmung von Lösungen in ICSPs (vgl. Cleary, 1987). Die Grundidee ist, dass Intervallarithmetik auf Subintervalle angewendet wird, um so engere Grenzen für die Ergebnisintervalle zu erhalten. Ziel von Cleary war es, ein Intervall-Constraint-Framework für CLP-Systeme zur Verfügung zu stellen, dass neben der Intervallrepräsentation ein einfaches Lösungsverfahren anbietet.

Die Suche im Lösungsraum gestaltet sich in der Form, dass Cleary abwechselnd die Wertebereiche der Intervalle zerteilt (engl. splitting) und anschließend Berechnungen zum weiteren Einschränken der Intervallgrenzen auf diesen Teilintervallen in separaten ICSPs anstellt (engl. squeezing). Die resultierende Backtracking-Suche im Lösungsbaum ist an einem einfachen Beispiel in Abbildung 5.22 dargestellt. Die notwendigen Berechnungen ergeben sich aus ableitbaren Funktionen, was sich bei Grundoperatoren trivial gestaltet.5.90 Die sich ergebenen Einschränkungen der Intervallgrenzen werden so lange durchgeführt, bis durch das Suchverfahren eine Lösung gefunden wird. Cleary (1987) beschränkt sich auf Grundoperatoren und ununterbrochene Intervalle.5.91

Abbildung 5.22: Einfaches Beispiel für Domänen-Splitting (vgl. Cleary, 1987, S. 135)
\begin{figure}\centering
\includegraphics[width=9.5cm]{images/constraints_splitting}
\ifx\pdfoutput\undefined
\fi
\end{figure}

Weiterentwicklungen und Optimierungen zum Domänen-Splitting betreffen Verbesserungen des Suchvorgangs und der Splitting-Strategie. Jussien et al. (1997) bzw. Jussien und Lhomme (1998) wenden eine dynamische Backtracking-Variante an, um den Splitting-Prozess effizienter zu gestalten (engl. dynamic domain splitting). Dynamic Backtracking ist eine Variante von abhängigkeitsgesteuertem Backtracking, welche sämtliche getestete Wertekombinationen speichert, anstatt sie, wie klassisches Backtracking, zu verwerfen, wenn eine Inkonsistenz auftritt. Dadurch ist es möglich, allerdings bei zusätzlichem Verwaltungsaufwand und erhöhter Speicherintensität, dynamisch unterschiedliche Stellen im Suchbaum zu bearbeiten, anstatt diesen, wie beim klassischen Backtracking, ausschließlich von oben nach unten zu durchlaufen (vgl. Ginsberg, 1993).

Silaghi et al. (1999) entwickeln ein Verfahren, dass informiert vorgeht5.92 und die Splitting-Punkte intelligent auswählt (engl. intelligent domain splitting). Benachbarte Regionen, die Lösungen beinhalten, werden auf diese Weise nicht zerteilt, wodurch der Splitting-Prozess effektiver wird, da insgesamt weniger ,,Splittings`` erforderlich sind. Das Verfahren ist allerdings aufgrund der Repräsentation der Wertebereiche auf finite Domänen begrenzt. Um diesen Effekt für kontinuierliche Wertebereiche nutzen zu können, wird z.B. Clustering eingesetzt. Bei der Clusteranalyse werden Algorithmen eingesetzt, die mittels Heuristiken Abschätzungen über zusammenhängende Bereiche des Lösungsraums vornehmen, und aufgrund dessen die Splitting-Strategie bestimmen (vgl. Vu et al., 2003b,a).

Domänen-Splitting ist ein gängiges Verfahren, wenn punktgenaue, kanonische Lösungen benötigt werden. Allerdings mündet das Verfahren bei größeren Constraint-Netzen schnell in einer kombinatorischen Explosion, da u.U. sehr viele Suchzweige berücksichtigt werden müssen (vgl. Lhomme, 1993, S. 236 f.). Es bietet sich daher an, Domänen-Splitting mit Filtermechanismen in Form von Konsistenzverfahren zu kombinieren (vgl. Van Hentenryck et al., 1997).5.93



Fußnoten

...5.90
Beispielsweise $(v_1+v_2=v_3)$, $(v_3-v_1=v_2)$, $(v_3-v_2=v_1)$.
...5.91
Cleary nennt die Eigenschaft eines ununterbrochenen Intervalls interval convexity und hebt die vereinfachte Berechnung mit diesen hervor (vgl. Cleary, 1987, S. 132).
...5.92
Das heißt die Constraints werden berücksichtigt.
...5.93
Häufig engl. Branch & Prune genannt.

next up previous contents index
Nächste Seite: 5.3.3 Label Inference Aufwärts: 5.3 Intervall Constraint Satisfaction Vorherige Seite: 5.3.1.4 Konvexität und Diskontinuität   Inhalt   Index