Constraint-Satisfaction-Problem

Ein Constraint-Satisfaction-Problem (CSP; deutsch: Bedingungserfüllungsproblem) 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.

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. Einfache Beispiele für solche Probleme sind das Damenproblem, das Vier-Farben-Problem, Sudoku, Str8ts oder das Erfüllbarkeitsproblem der Aussagenlogik (SAT bzw. SAT-k), Erfüllbarkeitsproblem für quantifizierte boolesche Formeln, Graphenfärbung oder Erfüllbarkeitsproblem für Schaltkreise, aber auch physikalische Probleme wie das Isingmodell und andere Spinmodelle auf Gittern. Dem entspricht in der elementaren Mathematik das Lösen einer Gleichung oder eines Gleichungssystems – als Constraint-Satisfaction-Probleme bezeichnet man speziell die Fragestellungen, die sich analytisch so nicht oder nur aufwändig lösen lassen.

Ein CSP wird gelöst, indem eine Belegung der Variablen gefunden wird, die allen Bedingungen genügt. Im Unterschied zu anderen Optimierungsproblemen, in denen eine „möglichst gute“ Lösung gesucht wird, fordern Constraint-Satisfaction-Probleme eine vollständige Erfüllung jeder einzelnen Vorbedingung. Sind die aufgestellten Bedingungen widersprüchlich, so gibt es keine Lösung des Problems (respektive umgekehrt: gibt es nachweislich keine Lösung, sind die Vorbedingungen als unvereinbar bewiesen). Es kann aber durchaus mehrere oder viele Lösungen geben. Gibt es nur eine, spricht man wie bei anderen Optimierungsfragen von einer „eindeutigen Lösung“ und bei dem entsprechenden SAT-Problem zu entscheiden, ob es nur eine Lösung gibt von unique SAT.

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.

Die CSP sind ein häufiger Testboden für Methoden der Komplexitätstheorie. Für die Komplexität in einer breiten Klasse von CSP-Abzählproblemen wurde 2021 der Gödel-Preis an Andrei Bulatov, Martin Dyer, David Richerby, Jin-Yi Cai und Xi Chen verliehen. Die Dichotomie besteht darin, dass sie entweder in Polynomzeit lösbar sind oder Sharp-P-schwer sind.^[1]

Literatur

• Krzysztof Apt; Principles of constraint programming. Cambridge University Press, 2003, ISBN 0-521-82583-0.
• Rina Dechter: Constraint processing. Morgan Kaufmann, 2003, ISBN 1-55860-890-7.
• Christophe Lecoutre: Constraint Networks: Techniques and Algorithms. ISTE/Wiley, 2009, ISBN 978-1-84821-106-3.
• David Poole, Alan Mackworth: Artificial Intelligence: Foundations of Computational Agents. Cambridge University Press, 2010; Kapitel 4.2.2 Constraint Satisfaction Problems (online, artint.info).

Einzelnachweise

1. Gödel Prize 2021