Einführung Constraints

Motivation: Einfärben von Landkarten

Die Skizze soll eine Landkarte mit verschiedenen Ländern darstellen. Die Aufgabe lautet: Färbe jedes Land mit einer Farbe ein, um die Übersichtlichkeit zu erhöhen. Verwende dabei so wenig wie möglich unterschiedliche Farben. Aneinander grenzende Länder müssen unterschiedliche Farben bekommen (=> Constraint).

Einfärben von Landkarten: Formalisierung

• Variablen: A, B, C, D, E, F

• Werte: $\lbrace red, green, blue \rbrace$

• Constraints: Benachbarte Regionen müssen unterschiedliche Farben haben

• Mögliche Lösung: Zuweisung an Variablen ("Belegung") $\lbrace \operatorname{A} = red, \operatorname{B} = blue, \operatorname{C} = green, \operatorname{D} = red, \operatorname{E} = blue, \operatorname{F} = blue \rbrace$

Definition: Constraint Satisfaction Problem (CSP)

• Ein CSP $\langle V, D, C \rangle$ besteht aus:

  • Menge von Variablen $V = \lbrace V_1, V_2, \ldots, V_n \rbrace$
  • Je $V_i$ nicht leere Domäne $D_i = \lbrace d_{i,1}, d_{i,2}, \ldots, d_{i,m_i} \rbrace$
  • Menge von Constraints $C = \lbrace C_1, C_2, \ldots, C_p \rbrace$ (Randbedingungen, Abhängigkeiten zwischen Variablen)

• Zuweisung/Belegung (Assignment) $\alpha$:

  • Zuweisung von Werten an (einige/alle) Variablen: $\alpha = \lbrace X=a, Y=b, \ldots \rbrace$ (aus den jeweiligen Wertebereichen)
  • Konsistente Belegung: Randbedingungen sind nicht verletzt
  • Vollständige Belegung: Alle Variablen sind belegt

• Lösung eines CSP: Vollständige und konsistente Belegung

Constraint-Graph

Ein CSP kann man auch als Constraint-Graph darstellen. Die Variablen werden zu Knoten im Graph, die Constraints zu Kanten zwischen den Knoten. Dadurch kann man die aus dem Problemlösen bekannten Algorithmen anwenden ...

Constraints -- Arität

Die Arität betrifft hier die "Stelligkeit": Wie viele Variablen stehen in einem Constraint miteinander in Beziehung? (Also wie viele Parameter hat ein Constraint?)

• unär: betrifft einzelne Variablen Beispiel: $\operatorname{A} \neq red$

• binär: betrifft Paare von Variablen Beispiel: $\operatorname{A} \neq \operatorname{B}$

• höhere Ordnung: betrifft 3 oder mehr Variablen

• Präferenzen: "soft constraints" Beispiel: "rot ist besser als grün"

  Abbildung über Gewichtung => Constraint-Optimierungsproblem (COP)

Constraints -- Wertebereiche

• Endliche Domänen: $d$ Werte => $O(d^n)$ mögliche Zuweisungen (exponentiell in der Zahl der Variablen)

• Unendliche Domänen: reelle Zahlen, natürliche Zahlen => Keine Auflistung der erlaubten Wertekombinationen mehr möglich => Übergang zu Gleichungen/Ungleichungen: $job_1+5

  • lineare Constraints
  • nichtlineare Constraints

Historische Unterscheidung:

• Constraint Satisfaction: endliche Domänen, kombinatorische Methoden
• Constraint Solving: unendliche Domänen

CSP sind überall ...

• Stundenpläne (Klassen, Räume, Zeiten)
• Konfiguration (Computer, Autos, ...)
• Fahrpläne (Zug, Flug, ...)
• Planung von komplexen Projekten
• Sudoku :-)
• ...

Wrap-Up

• Definitionen und Begriffe:
  • Variable, (un-) endliche Domänen, Wertemenge
  • Constraint, Arität, CSP
  • Zuweisung, Lösung, ...