Constraint-Satisfaction-Probleme

Ein Constraint-Satisfaction-Problem (CSP) fragt nach einer Zuweisung von Werten zu einer Menge von Variablen, die gleichzeitig alle Einschränkungen (Constraints) zwischen ihnen erfüllt, und bietet eine einheitliche Darstellung für viele kombinatorische Probleme.

Definition

Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Variablen, einer Domäne möglicher Werte für jede Variable und einer Menge von Constraints, die zulässige Wertekombinationen spezifizieren; eine Lösung ist eine vollständige Zuweisung, die keine Constraint verletzt.

Scope

Dieses Thema behandelt den Formalismus von Constraint-Satisfaction-Problemen (Variablen, Domänen, Constraints) und die Algorithmen, die sie lösen: Backtracking-Suche mit Heuristiken zur Variablen- und Wertreihenfolge, Constraint-Propagation und Konsistenztechniken (Knoten-, Kanten- und Pfadkonsistenz, wie der AC-3-Algorithmus) sowie die Ausnutzung der Problemstruktur (baumstrukturierte CSPs, Cutset Conditioning). Es besteht eine Verbindung zur lokalen Suche für CSPs und zur breiteren Praxis der Constraint-Programmierung. Die kontinuierlichen Optimierungs- und lernbasierten Formulierungen ähnlicher Probleme sind hier nicht Gegenstand der Betrachtung.

Core questions

• Wie werden diverse Probleme (Terminplanung, Kartenfärbung, Rätsel) einheitlich als Variablen, Domänen und Constraints dargestellt?
• Wie beschneidet die Constraint-Propagation Werte vor und während der Suche, um Backtracking zu reduzieren?
• Welche Heuristiken zur Variablen- und Wertreihenfolge machen die Backtracking-Suche effizient?
• Wie kann die Struktur des Constraint-Graphen (zum Beispiel baumförmig) für eine effiziente Lösung genutzt werden?

Key concepts

• Variablen, Domänen, Constraints
• Constraint-Graph
• Backtracking-Suche
• Forward Checking
• Kantenkonsistenz (Arc Consistency) und AC-3
• Heuristik der minimal verbleibenden Werte (Minimum-Remaining-Values Heuristic)
• Constraint-Propagation
• baumstrukturierte CSPs und Cutset Conditioning

Key theories

Kantenkonsistenz (Arc Consistency) und Constraint-Propagation

Ein CSP ist kantenkonsistent, wenn jeder Wert jeder Variablen einen konsistenten Partner in jeder benachbarten Variablen hat; Algorithmen wie AC-3 erzwingen dies, indem sie wiederholt nicht unterstützte Werte entfernen, wodurch Domänen vor oder während der Suche oft drastisch verkleinert werden.

Backtracking-Suche mit Heuristiken

CSPs werden durch Tiefensuche mit Backtracking gelöst, was durch Heuristiken wie die Wahl der am stärksten eingeschränkten Variablen (Minimum Remaining Values), des am wenigsten einschränkenden Wertes und durch die Verknüpfung von Forward Checking oder Propagation zur frühzeitigen Erkennung von Sackgassen praktikabel gemacht wird.

Ausnutzung der Struktur

Wenn der Constraint-Graph ein Baum ist, kann ein CSP in linearer Zeit bezüglich der Anzahl der Variablen gelöst werden, und baumähnliche Strukturen können über Cutset Conditioning oder Baumzerlegung auf diesen Fall reduziert werden.

Clinical relevance

CSP-Techniken sind die Grundlage für Terminplanung und Stundenpläne, Ressourcenallokation, Produktkonfiguration, Hardware- und Software-Verifikation sowie für Rätsellöser wie Sudoku; Constraint-Programmiersprachen und darauf aufbauende Solver werden in der industriellen Planung und Operations Research weit verbreitet eingesetzt.

History

Constraint-Netzwerke entstanden in den 1970er Jahren aus Arbeiten zur Szenenbeschriftung und relationalen Konsistenz, wobei Mackworths Arbeit von 1977 die Knoten-, Kanten- und Pfadkonsistenz formalisierte. In den 1980er und 90er Jahren entwickelte sich das Feld zur Constraint-Programmierung, die im "Handbook of Constraint Programming" von 2006 konsolidiert wurde und ein Standardthema der KI bleibt.

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

Wie unterscheidet sich ein Constraint-Satisfaction-Problem von einem allgemeinen Suchproblem?

Ein allgemeines Suchproblem behandelt Zustände als Black Boxes, aber ein CSP legt die interne Struktur eines Zustands als Zuweisung zu Variablen unter Berücksichtigung von Constraints offen. Diese Struktur ermöglicht es CSP-Solvern, Constraint-Propagation und Ordnungsheuristiken zu verwenden, die generische Suchen nicht nutzen können.

Was bewirkt Kantenkonsistenz (Arc Consistency)?

Kantenkonsistenz entfernt Werte aus der Domäne einer Variablen, die keinen kompatiblen Wert in einer benachbarten Variablen haben, unter Berücksichtigung der Constraint zwischen ihnen. Das Erzwingen dieser Konsistenz vor und während der Suche beschneidet den Suchraum und kann manchmal ein Problem direkt ohne Backtracking lösen.