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):
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):
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 . 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):
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.