Was haben Typ-Inferenz, Sudoku, das 8-Queens-Problem, das Einfärben von Landkarten und das Erstellen von Stundenplänen gemeinsam?
Es handelt sich um eine bestimmte Art von Suchproblemen, wobei den Parametern (Variablen) Werte so zugewiesen werden müssen, dass Einschränkungen bzw. Relationen zwischen den Variablen gelten.
Ein Constraintproblem (CSP) besteht aus Variablen, die über Einschränkungen ("Constraints") verbunden sind. Jeder Variable wird eine Domäne (Wertebereich) zugeordnet.
Die Constraints können sich auf eine einzelne Variable beziehen ("unäre Constraints"), auf zwei Variablen ("binäre Constraints") oder auf mehr Variablen. Ein CSP kann als Graph dargestellt werden.
Eine "Belegung" ist eine Zuweisung von Werten an Variablen aus deren Domäne. Eine "konsistente" Belegung erfüllt die Constraints, eine "vollständige" Belegung belegt alle Variablen.
Eine Lösung für ein CSP ist eine vollständige und konsistente Belegung.
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).
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$
Ein CSP $\langle V, D, C \rangle$ besteht aus:
Zuweisung/Belegung (Assignment) $\alpha$:
Lösung eines CSP: Vollständige und konsistente Belegung
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 ...
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)
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
Historische Unterscheidung:
CSP's mit endlichen Domänen lassen sich mit einer Backtracking-Suche lösen. Dabei wird schrittweise eine Variablen ausgewählt und dann ein Wert aus deren Wertebereich für die Belegung ausgewählt. Danach ruft sich die Backtracking-Suche rekursiv auf. Falls dabei keine Lösung gefunden werden kann, erfolgt Backtracking und die Belegung wird schließlich rückgängig gemacht und durch die nächste Möglichkeit ersetzt.
def BT_Search(assignment, csp):
if complete(assignment): return assignment
var = VARIABLES(csp, assignment)
for value in VALUES(csp, var):
if consistent(value, var, assignment, csp):
assignment += {var = value}
if INFERENCE(csp, assignment, var) != failure:
result = BT_Search(assignment, csp)
if result != failure: return result
assignment -= {var = value}
return failureQuelle: Eigener Code basierend auf einer Idee nach [Russell2020, p. 176, fig. 5.5]
Hierbei handelt es sich um eine etwas angepasste Tiefensuche: Starte mit leerem Assignment und weise schrittweise Variablen passende Werte zu und mache notfalls Backtracking.
CSP's mit endlichen Domänen lassen sich mit einer Backtracking-Suche lösen. Dabei gibt es einige Freiheitsgrade: Auswahl der nächsten Variable und Wahl des nächsten Werts. Hier können Heuristiken die Suche beschleunigen.
Zur Wahl der als nächstes zu betrachtenden Variable kann die Minimum Remaining Values (MRV)-Heuristik eingesetzt werden: Wähle die Variable mit wenigsten freien Werten. Bei Gleichstand bei der MRV kann man mit der Gradheuristik die Variable mit den meisten Constraints zu offenen (noch nicht belegten) Variablen wählen.
Bei der Wahl des Wertes kann die Least Constraining Value (LCV)-Heuristik genutzt werden: Wähle den Wert, der für die verbleibenden Variablen die wenigsten Werte ungültig macht.
Während die MRV relativ leicht umzusetzen ist, muss man für die LCV alle Constraints zu den Nachbarn auswerten.
VARIABLES: Welche Variable zuerst ausprobieren?
Minimum Remaining Values (MRV): (vgl. [Russell2020, S. 177])
Wähle Variable mit wenigsten freien Werten (die am meisten eingeschränkte Variable)
=> reduziert den Verzweigungsgrad
Beispiel:
VARIABLES: Welche Variable zuerst ausprobieren?
Gradheuristik: Erweiterung von MRV bei Gleichstand (vgl. [Russell2020, S. 177])
Wähle Variable mit meisten Constraints auf offene (noch nicht zugewiesene) Variablen
=> reduziert den Verzweigungsgrad in späteren Schritten
Beispiel:
VALUES: Welchen Wert zuerst ausprobieren?
Least Constraining Value (LCV): (vgl. [Russell2020, S. 177])
Wähle Wert, der für verbleibende Variablen die wenigsten Werte ungültig macht
=> verringert die Wahrscheinlichkeit für Backtracking
Beispiel:
Hinweis: Diese Heuristik ist in der Praxis sehr aufwändig zu berechnen! Man müsste für jeden Wert die noch offenen Constraints anschauen und berechnen, wie viele Werte damit jeweils ungültig gemacht werden. Die Idee ist aber dennoch interessant, und möglicherweise kann man sie für ein reales Problem so adaptieren, dass bei der Umsetzung nur wenig zusätzlicher Aufwand entsteht.
Sei $D=\lbrace 0, \ldots, 5 \rbrace$, und ein Constraintproblem definiert durch
$$\langle \lbrace v_1, v_2, v_3, v_4 \rbrace, \lbrace D_{v_1} = D_{v_2} = D_{v_3} = D_{v_4} = D \rbrace, \lbrace c_1, c_2, c_3, c_4 \rbrace \rangle$$mit
Bei der Backtracking-Suche werden schrittweise Variablen belegt. Dabei kann eine Belegung eine Lösung im weiteren Verlauf der Suche unmöglich machen, so dass (viel) Backtracking notwendig wird.
Beim Forward Checking entfernt man nach der Belegung einer Variablen in allen Nachbarvariablen die durch die aktuelle Belegung inkonsistent gewordenen Werte. Wenn dabei ein Wertebereich leer wird, führt die aktuelle Belegung nicht zu einer Lösung und kann sofort zurückgenommen werden. Allerdings findet man mit Forward Checking nicht alle Inkonsistenzen.
Bei der Kantenkonsistenz prüft man, ob zu jedem Wert aus dem Wertebereich einer Variablen in den Nachbarvariablen mindestens ein passender (konsistenter) Wert existiert. Dabei werden die Constraints nacheinander betrachtet (nicht gleichzeitig). Wenn dies nicht der Fall ist, wird der Wert aus dem Wertebereich der betrachteten Variablen entfernt. Der AC-3-Algorithmus erzeugt schrittweise Kantenkonsistenz für ein CSP.
Man kann den AC-3 als Vorverarbeitung nutzen und die Wertemengen vor der BT-Suche reduzieren. Eventuell findet man dabei bereits eine Lösung oder kann eine Lösung ausschließen. Man kann den AC-3 auch als Inferenzschritt in die BT-Suche einbetten ("MAC").
Zuweisung eines Wertes an Variable $X$:
Lösung: Nach Zuweisung alle nicht zugewiesenen Nachbarvariablen prüfen
Inference: Frühzeitiges Erkennen von Fehlschlägen! (vgl. [Russell2020, S. 178])
Nach Zuweisung eines Wertes an Variable $X$:
Beispiel:
Problem: Für B und C bleibt nur noch blau; sind aber benachbart!
Forward Checking erzeugt Konsistenz für alle Constraints der gerade betrachteten (belegten) Variablen.
Idee: Ausdehnen auf alle Kanten ... => Einschränken der Wertemengen
Eine Kante von $X$ nach $Y$ ist "konsistent", wenn für jeden Wert $x \in D_X$ und für alle Constraints zwischen $X$ und $Y$ jeweils ein Wert $y \in D_Y$ existiert, so dass der betrachtete Constraint durch $(x,y)$ erfüllt ist.
Ein CSP ist kanten-konsistent, wenn für alle Kanten des CSP Konsistenz herrscht.
$D_a=D_b=D_c=\lbrace 1,2,3 \rbrace$, $D_d=\lbrace 1,2 \rbrace$, $D_e=\lbrace 1,2,3 \rbrace$
Einschränkung der Ausgangswertemengen (kanten-konsistent)
$D_a=\lbrace 1,2,3 \rbrace$, $D_b=\lbrace 1,2 \rbrace$, $D_c=\lbrace 1,2 \rbrace$, $D_d=\lbrace 1,2 \rbrace$, $D_e=\lbrace 2,3 \rbrace$
=> Kantenkonsistenz ist nur lokale Konsistenz!
Anmerkung: $((a,b), \ne)$ ist Kurzform für $\left((a,b), \lbrace (x,y) \in D_a \times D_b | x \ne y \rbrace\right)$
def AC3(csp):
queue = Queue(csp.arcs)
while not queue.isEmpty():
(x,y) = queue.dequeue()
if ARC_Reduce(csp,x,y):
if D_x.isEmpty(): return false
for z in x.neighbors(): queue.enqueue(z,x)
return true
def ARC_Reduce(csp, x, y):
change = false
for v in D_x:
if not (any w in D_y and csp.C_xy(v,w)):
D_x.remove(v); change = true
return changeQuelle: Eigener Code basierend auf einer Idee nach [Russell2020, p. 171, fig. 5.3]
Anmerkung: Die Queue in AC-3 ist wie eine (mathematische) Menge zu betrachten: Jedes Element
kann nur genau einmal in einer Menge enthalten sein. D.h. wenn man bei queue.enqueue(z,x) die
Rückkanten von den Nachbarn in die Queue aufnimmt, sorgt die Queue eigenständig dafür, dass es
keine doppelten Vorkommen einer Kante in der Queue gibt. (Falls die verwendete Queue in einer
Programmiersprache das nicht unterstützt, müsste man bei queue.enqueue(z,x) stets abfragen, ob
die Kante (z,x) bereits in der Queue ist und diese dann nicht erneut hinzufügen.)
AC-3 hat eine Laufzeit von $O(d^3n^2)$ ($n$ Knoten, maximal $d$ Elemente pro Domäne). Leider findet
auch AC-3 nicht alle Inkonsistenzen ... (NP-hartes Problem).
Hinweis: In gewisser Weise kann man Forward Checking als ersten Schritt bei der Herstellung von Kantenkonsistenz interpretieren.
Vorverarbeitung: Reduktion der Wertemengen vor BT-Suche
Propagation: Einbetten von AC-3 als Inferenzschritt in BT-Suche (MAC -- Maintaining Arc Consistency)
Fingerübungen
Ist die Kante zwischen a und b konsistent?
Wann ist der Graph lokal konsistent?
Wie sieht die Queue im nächsten Schritt mit AC3 aus?
Aktuelle Queue: [ab, ac, ba, bc, ca, cb]