Quellenangabe

Die nachfolgenden Beschreibungen basieren auf dem Standardwerk zur künstlichen Intelligenz: „Artificial Intelligence – Modern Approach“ von Stuart Rusell und Peter Norvig

Was ist ein CSP-Problem?

Ein Constraint-Satisfaction-Problem oder kurz CSP bezeichnet Probleme, deren

• jeder Zustand durch eine Menge von Variablen dargestellt werden kann,

• wobei jede Variable jeweils einen Wert besitzt.

Zu einem CSP gehören weiterhin

• eine Reihe von Bedingungen, die erlaubte Kombinationen von Werten einer Gruppe von Variablen des CSP beinhaltet.

Ein CSP-Problem gilt dann als gelöst, wenn jede Variable einen Wert hat, der alle Bedingungen - Constraints genannt - für die Variable erfüllt.

Wie kann ein CSP-Problem gelöst werden?

CSP-Suchalgorithmen machen sich die Struktur von Zuständen zunutze und verwenden allgemeine statt domänenspezifische Heuristiken, um zur Lösung komplexer Probleme zu kommen.

Die generelle Idee besteht darin, durch die Identifizierung von Variable-Wert-Kombinationen, die die Constraints verletzen, große Teile des Suchraums auf einmal zu eliminieren.

CSPs haben außerdem den Vorteil, dass die Aktionen und das Transitionsmodell aus der Problembeschreibung wie folgt abgeleitet werden können:

Ein Constraint-Satisfaction-Problem besteht aus den drei Komponenten X, D, und C:

X ist eine Menge von Variablen, {X1,..., Xn}.

D ist eine Menge von Domänen, {D1,..., Dn), eine für jede Variable.

C ist eine Menge von Constraints, die erlaubte Kombinationen von Werten angeben.

Eine Domäne Di besteht aus einer Menge zulässiger Werte (v1,..., vk) für die Variable Xi. Eine boolesche Variable hätte zum Beispiel die Domäne (wahr, falsch). Unterschiedliche Variablen können unterschiedliche Domänen unterschiedlicher Größe haben.

Jeder Constraint Cj besteht aus einem Paar (scope, rel), wobei

• scope ein Tupel von Variablen ist, die in dem Constraint vorkommen, und

• rel eine Relation, welche die für diese Variablen möglichen Werte definiert.

Eine Relation kann als explizite Menge aller Tupel von Werten dargestellt werden. die den Constraint erfüllen, oder als Funktion, die berechnen kann, ob ein Tupel ein Element der Relation ist. Wenn z.B. X1 und X2 beide die Domäne {1,2,3) haben, dann kann der Constraint, dass X1, größer als X2 sein muss, als ((X1, X2), ((3, 1), (3,2), (2, 1))) oder als ((X1, X2), X1 > X2) geschrieben werden.

CSPs befassen sich mit der Zuweisung von Werten zu Variablen, {Xi = vi. Xj = vj,.....}. Eine Zuweisung, die kein Constraint verletzt, wird als konsistente oder zulässige Zuweisung bezeichnet. Eine vollständige Zuweisung ist eine Zuweisung, bei der jeder Variablen ein Wert zugewiesen wird, und eine Lösung eines CSP ist eine konsistente, vollständige Zuweisung.

Eine partielle Zuweisung ist eine Zuweisung, bei der nicht allen Variablen Werte zugewiesen sind, und eine partielle Lösung ist eine partielle Zuweisung, die konsistent ist. Das Lösen eines CSP ist im Allgemeinen ein NP-vollständiges Problem. obwohl es wichtige Unterklassen von CSPs gibt, die sehr effizient gelöst werden können.

Inferenz in CSP, Kantenkonsistenz und der AC-3 Algorithmus

Ein CSP-Algorithmus hat mehrere Möglichkeiten um zu einer Lösung zu kommen. Er kann Nachfolger erzeugen, indem er eine neue Variablenzuweisung wählt, oder er kann eine bestimmte Art von Inferenz durchführen, die als Constraint-Propagation bezeichnet wird, d.h., er verwendet Constraints, um die Anzahl der zulässigen Werte für eine Variable zu reduzieren, was wiederum die zulässigen Werte für eine andere Variable reduzieren kann, und so weiter.

Der Gedanke dabei ist, dass dadurch weniger Möglichkeiten bleiben, die bei der nächsten zu wählenden Variablenzuweisung berücksichtigt werden müssen.

Constraint-Propagation kann entweder mit der nachfolgenden Backtracking-Suche verknüpft werden oder als Vorverarbeitungsschritt ausführen, noch bevor die Suche beginnt. Manchmal kann diese Vorverarbeitung das gesamte Problem bereits lösen, sodass sich eine Backtracking-Suche erübrigt.

Die dahinterstehende Idee ist die lokale Konsistenz. Wenn wir jede Variable als einen Knoten in einem Graphen behandeln und jeder binäre Constraint als eine Kante, dann kann ein Prozess, der in jedem Teil des Graphen die Einhaltung der lokalen Konsistenz gewährleistet, bewirken, dass inkonsistente Werte im gesamten Graphen eliminiert werden.

Es gibt verschiedene Arten von lokaler Konsistenz, wobei wir uns nachfolgen auf die Kantenkonsistenz konzentrieren:

Eine Variable in einem CSP ist kantenkonsistent, wenn jeder Wert in ihrer Domäne die binaren Constraints der Variablen erfüllt. Formaler kann man auch sagen, Xi ist in Bezug auf eine andere Variable Xj kantenkonsistent, wenn es für jeden Wert in der aktuellen Domäne Di einen Wert in der Domäne Dj gibt, der den binären Constraint auf der Kante (Xi, Xj) erfüllt. Ein Graph ist kantenkonsistent, wenn jede Variable mit jeder anderen Variable kantenkonsistent ist.

Betrachten wir zum Beispiel den Constraint Y = X2, wobei die Domäne von X als auch von Y die Menge der Dezimalzahlen ist. Wir können diesen Constraint explizit schreiben als: {(X, Y), {(0,0). (1,1), (2,4), (3,9)}}

Um X in Bezug auf Y kantenkonsistent zu machen, reduzieren wir die Domäne von X auf {0,1,2,3). Wenn wir Y auch in Bezug auf X kantenkonsistent machen wollen, dann wird die Domäne von Y zu {0,1,4,9} und damit das gesamte CSP kantenkonsistent.

Der bekannteste Algorithmus, der die Einhaltung der Kantenkonsistenz gewährleistet, heißt AC-3 (siehe unten). Um jede Variable kantenkonsistent zu machen, verwaltet der AC-3 eine Warteschlange der zu berücksichtigenden Kanten.

Am Anfang enthält die Warteschlange alle Kanten des CSP. (Jeder binäre Constraint wird zu zwei Kanten, eine in jede Richtung)

AC-3 holt dann eine beliebige Kante (Xi, Xj) aus der Warteschlange und macht Xi kantenkonsistent in Bezug auf Xj.

Bleibt Di dadurch unverändert, führt der Algorithmus einfach mit der nächsten Kante fort. Wenn dies aber Di ändert (die Domäne verkleinert), dann fügen wir der Warteschlange alle Kanten (Xk, Xi) hinzu, bei denen Xk ein Nachbar von Xi ist.

Dies ist erforderlich, weil die Änderung von Di zu weiteren Verkleinerungen von Dk führen könnte, auch wenn wir zuvor Xk berücksichtigt haben.

Wird Di auf nichts reduziert, so wissen wir, dass das gesamte CSP keine konsistente Lösung hat, und AC-3 kann sofort eine Fehlermeldung zurückgeben.

Andernfalls prüfen wir weiter und versuchen, Werte aus den Domänen von Variablen zu entfernen, bis sich keine Kanten mehr in der Warteschlange befinden.

Am Ende bleibt ein CSP übrig, das äquivalent zum ursprünglichen CSP ist - beide haben die gleichen Lösungen -, aber das kantenkonsistente CSP ist schneller zu durchsuchen, weil die Domänen seiner Variablen kleiner sind. In einigen Fällen wird das Problem dadurch vollständig gelöst (indem es jede Domäne auf die Größe 1 reduziert) und in anderen Fällen beweist es, dass keine Lösung existiert (in dem es eine Domäne auf die Größe 0 reduziert.)

Was hat Nerdy Sudoku damit zu zun?

Das populäre Sudoku-Rätsel hat Millionen von Menschen mit sogenannten Constraint-Satisfaction-Problemen (CSP) konfrontiert, auch wenn sie sich dessen vielleicht nicht bewusst waren. Natürlich gehört auch Nerdy Sudoku zu den CSP-Problemen.

Ein Nerdy Sudoku besteht aus 256 Feldern, von denen einige zunächst mit Hexadezimal-Ziffern von 0 bis F gefüllt sind. Die Aufgabe besteht darin, alle verbleibenden Felder so auszufüllen, dass keine Ziffer zweimal in einer Zeile, Spalte oder einem 4x4-Block erscheint. Eine Zelle, Spalte oder ein Block werden als Einheit bezeichnet.

Diese Nerdy Sudokus haben die Eigenschaft, dass es genau eine Lösung gibt. Während es sich als knifflig erweisen und zig Minuten dauern kann, ein Nerdy Sudoku „von Hand" zu lösen, kann ein CSP-Solver Tausende von Rätseln pro Sekunde bearbeiten.

Ein Sudoku kann dabei als ein CSP mit 256 Variablen betrachtet werden, eine für jedes Feld. Wir verwenden die Variablennamen A0 bis Af für die obere Zeile (von links nach rechts) bis hinzu letztlich P0 bis Pf für die untere Zeile. Die leeren Felder haben die Domäne (1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F) und die vorausgefüllten Felder haben eine Domäne, die aus einem einzigen Wert besteht. Außerdem gibt es 3x16=48 verschiedene Alldiff-Constraints, eine für jede Einheit (Zeile, Spalte und Kasten mit 16 Feldern):

Alldiff(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, Aa, Ab, Ac, Ad, Ae, Af)

Alldiff(B0, B1, B2, B3, B4, B5, B6, B7, B8, B9, Ba, Bb, Bc, Bd, Be, Bf)

• • •

Alldiff(A0, B0, C0, D0, E0, F0, G0, H0, I0, J0, K0, L0, M0, N0, O0, P0)

Alldiff(A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1, M1, N1, O1, P1)

• • •

Alldiff(A0, A1, A2, A3, B0, B1, B2, B3, C0, C1, C2, С3, D0, D1, D2, D3)

Alldiff(A4, A5, A6, A7, B4, B5, B6, B7, C4, C5, С6, C7, D4, D5, D6, D7)

• • •

Lassen Sie uns nun sehen, wie weit uns die Kantenkonsistenz mit AC-3 bringt. Nehmen wir an, dass die Alldiff-Constraints um binäre Constraints (wie A1 ‡ A2) erweitert wurden, sodass wir den AC-3-Algorithmus direkt anwenden können.

Betrachten wir eine beliebige Variable z.B. C6 mit einem leeren Feld, eingebunden in die Zeile C, in die Spalte 6 und dem Block (A4…D7).

Gemäß den Constraints können nun alle Werte aus der entsprechenden Zeile, Spalte und Block aus der Domäne von E6 entfernt werden. Damit wird zunächst die Komplexität des Sudoku CSP-Problems deutlich reduziert.

Wenn darüber hinaus für E6 eine Domäne mit nur einem Wert übrigbleibt, kennen wir die Antwort für C6.

Die Lösung für das Feld C6 hat aber Auswirkungen auf alle anderen freien Felder der zugehörigen Zeile C, Spalte 6 und Block (A4..D7) und kann die möglichen Werte dieser Domänen weiter reduzieren.

Die Inferenz wird entsprechend weiter fortgesetzt, bis AC-3 im optimalen Fall das gesamte Rätsel gelöst hat und alle Variablen ihre Domänen auf einen einzigen Wert reduziert haben.

Natürlich würde Sudoku bald seinen Reiz verlieren, ließe sich jedes Rätsel durch eine mechanische Anwendung von AC-3 lösen, und tatsächlich funktioniert AC-3 nur für einfache Sudokus.

Um schwere Rätsel effizient zu lösen, müssen wir intelligenter vorgehen. In der Tat liegt der Reiz von Sudokus für Rate-Profis darin, möglichst einfallsreich zu sein, wenn es um den Einsatz komplexerer Inferenzstrategien geht. Echte Rätselfans geben diesen Strategien sogar spezielle Namen, wie z. B. „Nacked Tupel - Stufe 3".

Diese Strategie funktioniert folgendermaßen: Finden Sie in einer beliebigen Einheit (Zeile, Spalte oder Kasten) drei Felder, die jeweils eine Domäne haben, die die gleichen drei Zahlen oder eine Teilmenge dieser Zahlen enthält. Zum Beispiel könnten die drei Domänen {1,8), (3,8) und {1,3,8) sein. Daraus ergibt sich, dass wir nicht wissen, welches Feld 1, 3 oder 8 enthält, aber wir wissen, dass die drei Zahlen auf die drei Felder verteilt sein müssen. Daher können wir 1, 3 und 8 aus den Domänen jedes anderen Felds in der Einheit entfernen.

Backtracking-Suche für CSPs

Manchmal, wie z.B. bei schweren Nerdy Sudoku Rätseln, können wir den Constraint-Propagation-Prozess mit AC-3 beenden und haben immer noch Variablen mit mehreren möglichen Werten. In einem solchen Fall müssen wir nach einer Lösung mit einem Backtracking-Suchalgorithmus suchen, die auf Basis partieller Zuweisungen arbeiten.

Die nachfolgende Abbildung zeigt ein Backtracking-Suchverfahren für CSPs. Der Algorithmus beruht auf einer beschränkten Tiefensuche.

Es wählt eine nicht zugewiesene Variable nach der anderen, probiert dann jeweils der Reihe nach alle Werte in der Domäne dieser Variable aus, indem versucht wird, die jeweilige Variable mithilfe eines rekursiven Aufrufs zu einer Lösung zu erweitern.

Wenn der Aufruf erfolgreich ist, wird die Lösung zurückgegeben, andernfalls wird die Zuweisung auf den vorherigen Zustand zurückgesetzt und wir versuchen es mit dem nächsten Wert. Wenn kein Wert erfolgreich war, wird eine Fehlermeldung zurückgegeben.

Man erkennt dabei schnell, dass bei vielen Variablen und vielen möglichen Ziffern, der Suchbaum schnell extrem ansteigen kann.

Daher ist ein CSP-Solver in der Kombination aus Vereinfachung mit AC-3 Algorithmus und nachfolgenden Backtracking-Search am effizientesten