Constraint Satisfaction Problem

Ein Constraint-Satisfaction-Problem (Bedingungserfüllungsproblem, abgekürzt CSP) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu finden, der alle aufgestellten Bedingungen (Constraints) erfüllt. Beispiele für solche Probleme sind das Damenproblem, das Vier-Farben-Problem, Sudoku oder das Erfüllbarkeitsproblem der Aussagenlogik.

Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Variablen, ihren Wertebereichen und den Bedingungen, die Verknüpfungen zwischen den Variablen herstellen und dadurch festlegen, welche Kombinationen von Werten der Variablen zulässig sind. Auf diese Weise lassen sich eine Vielfalt von Problemen aus Informatik, Mathematik und weiteren Anwendungsgebieten formulieren. Ein CSP wird gelöst, indem eine Belegung der Variablen gefunden wird, die allen Bedingungen genügt. Sind die aufgestellten Bedingungen widersprüchlich, so gibt es keine Lösung des Problems.

Constraint-Satisfaction-Probleme werden in verschiedene Beschränkungs- bzw. Bedingungstypen unterteilt:

• unäre Bedingungen (Bedingungen, die den Wert einer einzelnen Variable kontrollieren)
• binäre Bedingungen (Verknüpfungen zwischen zwei Variablen)
• Bedingungen höherer Ordnung (Verknüpfungen, die drei oder mehrere Variablen umfassen)

Zur Lösung von Constraint-Satisfaction-Problemen werden verschiedene Ansätze kombiniert:

• Aus bestehenden Bedingungen werden neue Bedingungen berechnet, die den Wertebereich von Variablen zusätzlich einschränken oder zu einem Widerspruch führen (Bedingungsfortpflanzung, engl. Constraint Propagation).
• Im Lösungsraum der Variablen wird systematisch nach einer Lösung gesucht.

Grundsätzlich können für die Lösung von CSPs allgemeine Suchalgorithmen verwendet werden. Allerdings lässt die Besonderheit der Problemklasse Algorithmen zu, die um einiges effizienter arbeiten als allgemeine Suchalgorithmen.

• Zustände sind durch Werte von Variablen definiert.
• Operatoren belegen eine Variable mit einem Wert.
• Der Zieltest wird durch Bedingungen spezifiziert, welche die Variablenbelegungen erfüllen müssen.
• Ein Zielzustand ist eine Belegung der Variablen mit Werten, die alle Bedingungen erfüllen.

Beispiele für Algorithmen, die sich besonders für die Lösung von Constraint-Satisfaction-Problemen eignen, sind der AC-3-Algorithmus, Backtracking oder die Min-Conflict-Heuristik.