Einführung

Beim Constraint Programming geht es primär darum ein Problem durch die Modellierung von Constraints zu definieren. Im Gegensatz zu herkömmlichen Algorithmen wird dabei nicht der Lösungsweg vorgegeben, sondern das Problem selbst beschrieben und über Constraints eingegrenzt.

Einsatz

Für den Einsatz von Constraint Programming eignen sich vor allem Probleme, die sich einfach durch Regeln und Gesätze ausdrücken lassen. So spielt Constraint Programming zum Beispiel in folgenden Bereichen eine Rolle:

• Elektrotechnik - Berechnung von Schaltplänen
• Mollekularbiologie - DNA Sequenzierung
• Termin-/Zeitplanung
• Auswahl und Planung der von Satelliten durchgeführten Beobachtungen

^[1]

Grundlagen

Um ein Problem mit dem Ansatz des Constraint Programming lösen zu können, muss es als Constraint Satisfaction Problem - CSP modelliert werden.

Constraint Satisfaction Problem

Ein Constraint Satisfaction Problem kann als Tripel <X,D,C> definiert werden, bestehend aus:

1. Die Variablen, die für die Lösung des Problems belegt werden müssen. Definiert durch Menge X:

X=\{x_1,...,x_n\}

2. Die Domänen, die den Wertebereich der Variablen einschränken. Definiert als eine Menge D, bestehend aus den Mengen des akzeptierten Wertebereich der jeweiligen Variablen:

D=\{D_1,...,D_n\}

3. Die Constraints, welche die Bedingungen formulieren. Definiert als eine Menge C:

C=\{c_1,...,c_m\}

Jedes Constraint c ist definiert als ein Paar < \sigma_c, \rho_c >, wobei:

• Der Scope \sigma_c \subseteq X die Menge der Variablen beschreibt, die von diesem Constraint betroffen sind.
• Die Relation \rho_c \subseteq \prod_{x \in \sigma_c} D_x die Menge der erlaubten Belegungen der Variablen im Scope darstellt.

Eine Belegung ist ein Tupel <x_i, a>, mit a \in D_i. Eine Belegung weist also einer Variablen ein Wert aus der jeweiligen Domäne zu.

Lösung

Um eine Lösung für ein Constraint Satisfaction Problem zu finden, suchen wir nach einer vollständigen Belegung, eine Menge an Belegungen, bei der jeder freien Variable ein Wert zugeteilt wird. Damit eine solche vollständige Belegung nun eine passende Lösung unseres Problems darstellt müssen alle Constraints eingehalten werden. Für alle Belegungen muss also gelten: wenn die Variable der Zuteilung x_i ein Element eines Scopes \sigma_c eines Constraints c ist, so muss die zugeteilte Wert a ein Element der Relation \rho_c sein.

^[2]

Solver

Für die Suche einer Lösung kommen Constraint Librarys zum Einsatz. Diese besitzen zur Lösungsfindung Constraint Solver - hoch optimierte Algorithmen, die sehr effizient den Suchbaum zu durchsuchen.

Suche

Die einfachste Suche stellt dabei ein einfacher Backtracking-Alogorithmus dar, welcher systematisch alle möglichen Belegungen ausprobiert und bei Verletzung eines Constraints zu einem vorherigen Zustand zurückspringt. Dieser Ansatz kann jedoch ineffizient sein, weshalb moderne Solver zahlreiche Optimierungen wie Heuristiken, Constraint Propagation und Konfliktanalyse einsetzen, um den Suchraum drastisch zu verkleinern. Im Folgenden wollen wir uns einige einfache Optimierungen genauer anschauen.

Forward Checking

Eine einfache Optimierung zum Backtracking-Algorithmus ist das Forward Checking. Dabei wird nach jeder Zuweisung einer Varibale alle Werte der Domänen der übrigen Varibalen entfernt, die im Konflikt mit der aktuellen Zuweisung stehen. Damit ist es möglich die Domänen und damit auch den Suchbaum schon frühzeitig im Verlauf deutlich einzuschränken und damit deutlich an Effizienz zu gewinnen.

Die Abbildung veranschaulicht Forward Checking am Beispiel des 6-queens Problems. Durch das Setzen einer Dame können wir nach jedem Zug schon Felder streichen, die im Konflikt mit der gerade gesetzten Dame stehen. Als Folge lässt sich der Suchbaum deutlich reduzieren.

MAC Algorithmus

Der MAC Algorithmus folgt einem ähnlichen Prinzip wie der Forward Checking Algorithmus. Jedoch geht er noch einen Schritt weiter indem nach jeder Zuweisung alle Werte der Domänen entfernt werden, die:

1. Nicht mit der aktuellen Zuweisung kompatibel sind.
2. Keinen passenden Wert in den Domänen anderer zukünftiger Variablen haben.

Damit lässt sich der Suchbaum noch einmal frühzeitg deutlich reduzieren.

^[3]

Referenzen

Abbildungen

• Abbildung 1: Aus Constraint satisfaction problems: Algorithms and applications.^[3:1]
• Abbildung 2: Aus Constraint satisfaction problems: Algorithms and applications.^[3:2]