next up previous contents index
Nächste Seite: 5.2.1 Historisches Beispiel Aufwärts: 5. Grundlegende Constraint-Lösungstechniken für Vorherige Seite: 5.1 Einführung   Inhalt   Index

5.2 Klassische Constraint Satisfaction Probleme

Das allgemeine Constraint Satisfaction Problem (CSP) bezeichnet eine Klasse von kombinatorischen Problemen, die mittels einer Menge von Randbedingungen bzw. Constraints über eine Menge von Variablen formuliert werden. Die Aufgabe besteht darin, eine wohlgeformte Belegung für eine endliche Menge von Variablen zu finden. Wohlgeformt bedeutet in diesem Fall eine konsistente Belegung der Variablen mit Werten, so dass alle Randbedingungen erfüllt werden.

Das CSP-Schema ist ein flexibler Ansatz zur natürlichen Problembeschreibung durch Constraints. Der Einsatz von Constraints erlaubt eine formale und deklarative Problembeschreibung, die von konkreten, domänenspezifischen Lösungsverfahren abstrahiert. Probleme werden als CSP formuliert, weil dadurch die Beantwortung bestimmter Fragestellungen durch spezielle Lösungsverfahren auf effiziente Weise ermöglicht wird (vgl. Kolbe, 2000, S. 37).

Die Ursprünge des CSP gehen zurück auf die Arbeit von Montanari (1974). Erstmals wurde ein reales Problem einer Anwendung von Waltz (1975) als CSP behandelt. Eine Erweiterung bzw. ein erster Vergleich verschiedener Lösungsverfahren wurde von Mackworth (1977a) vorgenommen. Eine gute Übersicht ist dem Lehrbuch von Tsang (1993) und den Übersichtsartikeln bzw. -kapiteln von Barták (1999a,b); Dechter (1999,1992); Dechter und Rossi (2003); Yang und Yang (1997); Ruttkay (1998); Güsgen (2000); Kumar (1992); Barták (2001); Russel und Norvig (2002) zu entnehmen. Das allgemeine CSP lässt sich auf die folgende, deklarative Weise definieren (vgl. Kolbe, 2000, S. 36):

Definition 5.2.1   (Constraint Satisfaction Problem, CSP)
Ein Constraint Satisfaction Problem wird durch ein Tripel $(V,D,C)$ beschrieben, wobei $V = \{v_1,\ldots,v_n\}$ eine endliche Menge von Variablen mit assoziierten Wertebereichen $D = \{D_1,\ldots,D_n\}$ mit $\{v_1 : D_1,\ldots,v_n : D_n\}$ ist. $C$ ist eine endliche Menge von Constraints $C_j(V_j)$, $j \in \{1,\ldots,m\}$, wobei jedes Constraint $C_j(V_j)$ eine Teilmenge $V_j = \{v_{j_1},\ldots,v_{j_k}\} \subseteq
V$ der Variablen zueinander in Relation setzt und deren gültige Wertekombinationen auf eine Teilmenge von $D_{j_1} \times \cdots
\times D_{j_k}$ beschränkt.

Zu beachten ist bei dieser allgemeinen Definition, dass die Wertebereiche der Variablen eines CSP nicht unbedingt auf Zahlenwerte beschränkt sein müssen. So können durchaus andere (symbolische) Domänen zum Einsatz kommen, die sich letztendlich allerdings durchaus wiederum als Zahlenwerte repräsentieren lassen.

Klassischerweise bezieht sich die Literatur bei der Definition von CSPs häufig auf eine strengere Form, in der die Domänen der Variablen aus diskreten, endlichen Mengen bestehen (vgl. Mackworth, 1977a; Waltz, 1975). Auch heute beschränken sich viele Lehrbücher und wissenschaftliche Veröffentlichungen bei der Definition von CSPs ausschließlich auf finite Domänen (vgl. Tsang, 1993; Kumar, 1992; Barták, 2001; Van Hentenryck, 1989). In der Vergangenheit wurden CSPs mit finiten Domänen in Anlehnung an Waltz (1975) auch als Consistent Labeling Problem benannt (vgl. Haralick und Shapiro, 1979; Tsang, 1993).5.2 In neueren Publikationen wird basierend auf dem Terminus von Mackworth (1992) zwischen dem allgemeinen CSP und dem Finite Constraint Satisfaction Problem (FCSP) unterschieden (vgl. Mackworth und Freuder, 1993; Meyer, 1995; Tsang, 1993), welches wie folgt definiert wird (vgl. Meyer, 1995, S. 28):

Definition 5.2.2   (Finite Constraint Satisfaction Problem, FCSP)
Sei $P = (V,D,C)$ ein CSP. Wenn die Domäne $D_i$ jeder Variablen $v_i
\in V$ diskret und endlich ist, wird P ein Finite Constraint Satisfaction Problem (FCSP) genannt.

Weil bei einem FCSP die Wertebereiche der Variablen endlich sind, ist auch der Lösungsraum endlich. Die Anzahl der möglichen Lösungen ergibt sich wiederum aus dem kartesischen Produkt aller Wertebereiche $D_1 \times \cdots \times D_n$. Die Kardinalität dieser Menge, und entsprechend auch der Aufwand zur Berechnung dieser möglichen Lösungen, wächst exponentiell mit der Anzahl der Variablen (vgl. Kolbe, 2000, S. 37). Das FCSP gehört zur Klasse der NP-vollständigen Probleme.5.3 Der formale Beweis für die NP-Vollständigkeit wird von Haralick und Shapiro (1979, S. 177) durch die Reduzierung des FCSP auf das SAT-Problem geführt.5.4

Eine weitere wichtige Klasse sind CSPs, die nur aus unären und binären Constraints bestehen. Sie lassen sich als Graph darstellen, indem die Variablen die Knoten und die binären Constraints die Kanten zwischen den Knoten repräsentieren. Unäre Constraints werden i.d.R. nicht explizit dargestellt, da sie den zugewiesenen Wertebereichen der Variablen entsprechen. Ein solcher Constraint-Graph wird entsprechend Constraint-Netz genannt. Ein binäres CSP wird wie folgt definiert (vgl. Tsang, 1993, S. 12):

Definition 5.2.3   (binäres CSP, allgemeines CSP)
Ein binäres Constraint Satisfaction Problem, oder binäres CSP, ist ein CSP mit ausschließlich unären und binären Constraints. Ein CSP, das nicht auf unäre und binäre Constraints beschränkt ist, wird allgemeines CSP genannt.

Die große Mehrzahl der Veröffentlichungen beschränkt sich auf die Behandlung von binären Constraints und entsprechend binären CSPs, was darin begründet liegt, dass zum einen diese Voraussetzung die Entwicklung von effizienten Lösungsverfahren vereinfacht und zum anderen jedes höherwertige Constraint mit einer Stelligkeit größer als zwei auf relativ einfache Weise in ein binäres Constraint überführt werden kann.

Constraints mit einer Stelligkeit höher als zwei werden auch n-äre Constraints bzw. non-binary oder high-order Constraints genannt. Spezielle Verfahren zur direkten Behandlung von n-ären Constraints bzw. zur Umwandlung von n-ären in binäre Constraints, werden in Abschnitt 5.2.6 ff. vorgestellt.



Fußnoten

...5.2
Die einzelnen Elemente der Wertebereiche einer Variable werden von Waltz (1975) als label (engl.: Marke, Markierung) bezeichnet.
...5.3
NP-vollständige Probleme gehören zu den schwierigsten Problemen in der Informatik. Ein Problem, das NP-vollständig ist, lässt sich nur von einem nichtdeterministischen Algorithmus in polynomialer Laufzeit lösen. Bisher konnte nicht gezeigt werden, dass ein NP-vollständiges Problem deterministisch in Polynomialzeit lösbar ist, womit ein offenes Problem der Informatik, nämlich ob $P = NP$ ist, gelöst wäre. Es besteht die starke Vermutung, dass $P \neq NP$ gilt, und somit kein NP-vollständiges Problem durch ein effizientes Verfahren gelöst werden kann vgl. Claus und Schwill, 2001, S. 448 ff.; Broy, 1995, S. 122.
...5.4
SAT: satisfiability problem, Erfüllbarkeitsproblem der Aussagenlogik (vgl. Claus und Schwill, 2001, S. 230).


Unterabschnitte
next up previous contents index
Nächste Seite: 5.2.1 Historisches Beispiel Aufwärts: 5. Grundlegende Constraint-Lösungstechniken für Vorherige Seite: 5.1 Einführung   Inhalt   Index