Constraint-Erfüllungsprobleme

Ein Constraint-Erfüllungsproblem, kurz CSP, beschreibt eine Reihe von Wahlmöglichkeiten und die Regeln, die sie verbinden. Sein Zustand ist eine faktorisierte Repräsentation: Du kannst einzelne Variablen und ihre Werte betrachten und dann allgemeine Verfahren zur Beschneidung und Suche wiederverwenden.

Variablen, Wertebereiche und Constraints

Eine Variable bezeichnet etwas, das gewählt werden muss. Ihr Wertebereich listet ihre erlaubten Werte auf. Ein Constraint legt fest, welche Kombinationen gemeinsam auftreten dürfen. Für die Workshops A und B sei jeder Wert ein Zeitfenster aus $\{1,2,3\}$. Die Regel „A findet vor B statt“ hat den Geltungsbereich $\{A,B\}$ und die Relation $\{(1,2),(1,3),(2,3)\}$. Die Schreibweise $A<B$ drückt dieselbe Relation kompakt aus.

Der Geltungsbereich benennt die beteiligten Variablen; die Relation gibt die erlaubten Wertetupel an. Wer beides verwechselt, erstellt möglicherweise ein Modell, in dem „Rot“ zur Variablen wird. Bei der Kartenfärbung sind Regionen Variablen und Farben Werte.

Was zählt als Lösung?

Eine Belegung weist Variablen Werte zu. Drei Prüfungen beschreiben ihren Status:

• Sie ist partiell, wenn einige Variablen keinen Wert haben.
• Sie ist vollständig, wenn jede Variable einen Wert hat.
• Sie ist konsistent, wenn sie keinen Constraint zwischen den belegten Variablen verletzt.

Eine Lösung muss vollständig und konsistent sein. Bei alleinigem $A=2$ ist die Belegung konsistent, aber partiell. Ergänzt man $B=1$, wird sie vollständig und inkonsistent. Mit $B=3$ ergibt sich eine Lösung für dieses Beispiel mit zwei Variablen. Eine konsistente partielle Belegung lässt sich möglicherweise dennoch nicht vervollständigen: Unbelegten Variablen können die passenden Wahlmöglichkeiten ausgehen.

Einen Constraint-Graphen interpretieren

Zeichne für ein binäres CSP pro Variable einen Knoten und für jedes durch einen Constraint verbundene Paar eine Kante. Auf einer vereinfachten Australienkarte sind die Variablen WA, NT, SA, Q, NSW, V und T, jeweils mit dem Wertebereich {Rot, Grün, Blau}. Die benachbarten Paare sind WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW und NSW–V. Jede Kante verlangt verschiedene Farben.

Eine Lösung ist WA Rot, NT Grün, SA Blau, Q Rot, NSW Grün, V Rot und T Rot. Prüfe jede Kante, auch SA–V. T hat keine Kante, daher ist seine Farbe unabhängig vom Festland. Es gibt 6 Färbungen des Festlands und 3 Möglichkeiten für T, also 18 Lösungen. Ein Constraint, der mehrere Variablen betrifft, benötigt eine Darstellung als Hypergraph; ein zusätzlicher Constraint-Knoten kann mit jeder Variablen in seinem Geltungsbereich verbunden werden.

Wertebereiche und Größe des Suchraums

Ein endlicher diskreter Wertebereich ist eine feste Liste, etwa drei Farben. Ein unendlicher diskreter Wertebereich könnte jede nichtnegative ganzzahlige Startzeit enthalten. Ein kontinuierlicher Wertebereich könnte reellwertige Zeiten enthalten. Die beiden letzteren benötigen Darstellungen und Verfahren, die zu diesen Wertebereichen passen; lineare Programmierung behandelt kontinuierliche lineare Constraints.

Für $n$ Variablen mit je $d$ Werten gibt es $d^n$ vollständige Belegungen. Die Karte hat $3^7=2187$ Kandidaten, bevor Constraints welche entfernen. Endliche CSPs umfassen NP-vollständige Probleme, daher ist kein allgemeines Lösungsverfahren mit polynomialer Laufzeit bekannt. Ihre innere Struktur ermöglicht dennoch Beschneidung: Der Löser kann eine Wahl ausschließen, ohne jede vollständige Belegung aufzulisten, die sie enthält. Ob die Antwort zulässig ist, hängt nur von den endgültigen Werten ab; der Weg, auf dem sie gefunden wurden, ist unerheblich.

Constraints unterscheiden sich darin, wie viele Variablen sie verbinden und ob sie Anforderungen oder Präferenzen angeben. Wenn du diese Struktur erkennst, kannst du ein wirklichkeitsgetreues Modell schreiben und geeignete Propagationsverfahren wählen.

Den Geltungsbereich einordnen

Ein unärer Constraint schränkt eine Variable ein. Kann Workshop E nicht in Zeitfenster 1 stattfinden, wende $E\mathrm{\ne }1$ an, indem du seinen Wertebereich vor der Suche von $\{1,2,3\}$ auf $\{2,3\}$ verkleinerst. Ein binärer Constraint setzt zwei Variablen zueinander in Beziehung, etwa $A<B$ oder $A\mathrm{\ne }D$. Ein binäres CSP enthält nur unäre und binäre Constraints.

Ein Constraint höherer Stelligkeit betrifft mindestens drei Variablen. Müssen die Aufgabendauern X, Y und Z 10 Stunden ausfüllen, schreibe $X+Y+Z=10$. Liegt jede Dauer in $\{1,2,3,4,5\}$, scheitert das Tupel $(2,3,4)$, während $(2,3,5)$ funktioniert. Bei der Prüfung einer höherstelligen Regel müssen die Werte zusammenpassen.

Nützliche globale Constraints beibehalten

Ein globaler Constraint gibt eine benannte Regel für eine Gruppe variabler Größe an. $\mathrm{Alldiff}(X_1,\dots ,X_k)$ verlangt für jedes Paar verschiedene Werte. Seine Lösungsmenge entspricht der durch $k(k-1)\mathrm{/}2$ paarweise Ungleichungen definierten Menge. Für neun Sudoku-Zellen sind das 36 binäre Constraints.

Die globale Form ermöglicht einem Löser außerdem Schlussfolgerungen über die Gruppe. Drei Variablen, die auf zwei verschiedene Werte beschränkt sind, können nicht alle verschieden sein, obwohl jedes Paar einzeln eine vereinbare Belegung hat. Gleiche Lösungsmengen garantieren keine gleich starke Beschneidung.

Auch eine Kapazitätsregel kann global sein. Hier bedeutet $\mathrm{Atmost}(10,P_1,P_2,P_3)$ dasselbe wie $P_1+P_2+P_3\le 10$: Die Gesamtzahl der Personen, die den drei Aufgaben zugeordnet sind, darf zehn nicht überschreiten. Die Argumente stehen für Größen, die addiert werden; daher erlaubt diese Regel zum Beispiel $(3,4,3)$.

Einen endlichen Constraint in binäre Form umwandeln

Führe eine Hilfsvariable U ein, deren Werte die erlaubten Tripel für $X+Y+Z=10$ sind. Ein möglicher Wert ist $(2,3,5)$. Füge drei binäre Constraints hinzu: Die erste Komponente von U ist gleich X, die zweite gleich Y und die dritte gleich Z. Wird dieser Wert für U gewählt, muss folglich $X=2$, $Y=3$ und $Z=5$ gelten.

Jedes ursprünglich zulässige Tripel entspricht einem Wert von U, und jede konsistente Belegung mit U ergibt ein gültiges ursprüngliches Tripel. Mit dieser Konstruktion können binäre Verfahren einen endlichen höherstelligen Constraint behandeln. Der Preis ist der möglicherweise große Tupelwertebereich, weshalb Löser oft die ursprüngliche globale oder höherstellige Regel beibehalten.

Anforderungen und Präferenzen

Mit weichen Constraints wird die Aufgabe zu einem Constraint-Optimierungsproblem, kurz COP: Erfülle alle harten Regeln und minimiere die Gesamtkosten der Präferenzen. Für die Optimierung können Branch-and-Bound und lokale Suche eingesetzt werden.

Teste das Modell an einer bekanntermaßen zulässigen und einer bekanntermaßen unzulässigen Belegung. Eine erfundene Ungleichung zwischen unabhängigen Workshops entfernt zulässige Zeitpläne; ein fehlender Constraint für eine gemeinsame Lehrkraft lässt unmögliche zu. Auch bei Präferenzen ist Vorsicht nötig: Wird aus „Nachmittag bevorzugt“ ein „Nachmittag erforderlich“, kann jeder zulässige Zeitplan ausgeschlossen werden.

Ein Modell sollte die Entscheidungen so direkt beschreiben, dass sich die Regeln leicht ausdrücken lassen. Bestimme zuerst, was gewählt werden muss, weise dann Wertebereiche zu und übersetze jede Anforderung über die Variablen, die sie tatsächlich betrifft.

Einen Workshop-Zeitplan erstellen

Fünf Workshops von je einem Zeitfenster teilen sich drei Zeitfenster: 1 Vormittag, 2 Mittag und 3 Nachmittag. A stehe für Python-Grundlagen, B für Python für Fortgeschrittene, C für Statistik, D für Datenbanken und E für Ethik. Jeder Workshop ist eine Variable mit dem anfänglichen Wertebereich $\{1,2,3\}$.

Gemeinsame Teilnehmende erfordern $A\mathrm{\ne }C$, $A\mathrm{\ne }D$, $C\mathrm{\ne }D$, $B\mathrm{\ne }C$, $C\mathrm{\ne }E$ und $D\mathrm{\ne }E$. Grundlagen muss vor Fortgeschrittene stattfinden, also $A<B$. Die Lehrkraft für Ethik kommt mittags an, also $E\mathrm{\ne }1$. Das ergibt sieben binäre Kanten und eine unäre Regel; C hat vier Nachbarn.

Die Belegung $A=2,B=3,C=1,D=3,E=2$ erfüllt jede Regel: Jedes Paar mit gemeinsamen Teilnehmenden ist verschieden belegt, Grundlagen findet vor Fortgeschrittene statt und Ethik liegt nicht in Zeitfenster 1. Sie ist die einzige zulässige Belegung unter den $3^5=243$ Kandidaten. Die Workshops B und D dürfen beide Zeitfenster 3 nutzen, weil keine Regel verschiedene Werte für sie verlangt.

Würde stattdessen pro Zeitfenster eine Variable gewählt, wäre jeder Wert eine Teilmenge der Workshops, mit bis zu $2^5=32$ möglichen Teilmengen pro Zeitfenster. Die Regeln müssten dann diese Mengen betrachten und sicherstellen, dass jeder Workshop einmal stattfindet. Werden Workshops als Variablen gewählt, bleiben die Constraints einfacher.

Aufgabenzeiten und gemeinsam genutzte Ressourcen ausdrücken

Verwende bei der Werkstattfertigungsplanung für jede Aufgabe eine Startzeitvariable. Vorbereiten dauert 20 Minuten, Analysieren 40 und Bericht erstellen 30. Die Startzeiten sind nichtnegative ganze Minuten. Die Reihenfolge und die Frist von 120 Minuten ergeben

Die frühesten Startzeiten sind 0, 20 und 60. Rechnet man von der Frist zurück, ergeben sich die spätesten Startzeiten 30, 50 und 90. Die Zeitfenster sind also $S_P\in [0;30]$, $S_A\in [20;50]$ und $S_R\in [60;90]$.

Zwei Aufgaben, die sich eine Maschine teilen, benötigen einen disjunktiven Constraint: $S_X+d_X\le S_Y$ oder $S_Y+d_Y\le S_X$. Jede der beiden Aufgaben darf zuerst kommen, aber sie dürfen sich nicht überschneiden. Eine einfache Vorrangbedingung würde eine bestimmte Reihenfolge erzwingen und die andere Möglichkeit ausschließen.

Zuordnungen und Rätsel modellieren

Für drei Berichte, die drei Prüfenden zugeordnet werden, machst du jeden Bericht zu einer Variablen mit Prüfenden als Werten. Verwende Alldiff, wenn jede prüfende Person einen Bericht bearbeitet. Ein Interessenkonflikt entfernt eine prüfende Person aus dem Wertebereich des betreffenden Berichts.

Beim n-Damen-Problem sei $Q_i$ die Zeile der Dame in Spalte $i$. Eine Dame pro Spalte ist im Modell angelegt. Verlange für jedes Paar $Q_i\mathrm{\ne }{Q}_j$ und $\mathrm{\mid }{Q}_i-Q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }$, um Angriffe in Zeilen und auf Diagonalen zu verhindern. Für acht Damen verringert dies den Raum der Möglichkeiten von der Wahl von 8 Feldern aus 64, also $\mathrm{4.426.165.368}$ Platzierungen, auf $8^8=\mathrm{16.777.216}$ Belegungen. Es gibt 92 Lösungen.

Bei Sudoku haben die 81 Zellvariablen die Wertebereiche 1–9. Vorgegebene Ziffern ergeben unäre Constraints, und die 9 Zeilen, 9 Spalten und 9 Boxen ergeben jeweils Alldiff.

Wähle die gröbsten Zeiteinheiten, die noch jeden erlaubten Beginn darstellen. Für Veranstaltungen zur vollen Stunde reichen stündliche Wahlmöglichkeiten; Wertebereiche in einzelnen Minuten würden den Aufwand vergrößern, ohne einen nützlichen Zeitplan hinzuzufügen. Trenne abschließend Präferenzen von harten Regeln und prüfe einen kleinen Fall mit bekannter Antwort.

Backtracking baut mittels Tiefensuche eine partielle Belegung auf. Es wählt eine Variable, versucht einen Wert und macht weiter, bis es eine Lösung findet oder eine Wahl rückgängig machen muss. Die Suche behält die brauchbaren früheren Entscheidungen bei, wenn eine spätere scheitert.

Nach Werten verzweigen, jeweils für eine Variable

A und dann B zu belegen ergibt dieselbe endgültige Belegung wie B und dann A zu belegen. Dank dieser Kommutativität kann ein CSP-Löser auf jeder Ebene eine Variable wählen und nach ihren Werten verzweigen. Würde jede Variablenreihenfolge zugelassen, ergäbe das $n!d^n$ Blätter für nur $d^n$ verschiedene vollständige Belegungen. Für fünf Variablen mit drei Werten sind das 29.160 Blätter statt 243.

Die nächste Variable kann von den aktuellen Wertebereichen abhängen. Entscheidend ist, an einem Knoten eine einzige nächste Variable zu wählen; die Suche benötigt keine getrennten Zweige für alle möglichen Belegungsreihenfolgen.

Die rekursiven Schritte nachvollziehen

1. Ist die Belegung vollständig und konsistent, gib sie zurück.
2. Wähle eine unbelegte Variable.
3. Versuche jeden Wert ihres Wertebereichs, der mit der aktuellen Belegung konsistent ist.
4. Rufe das Verfahren nach dem Hinzufügen eines Werts rekursiv auf. Scheitert der rekursive Aufruf, entferne diese Belegung und versuche den nächsten Wert.
5. Funktioniert kein Wert, gib einen Fehlschlag an den aufrufenden Schritt zurück.

Einfaches Backtracking prüft einen Constraint, sobald alle Variablen in seinem Geltungsbereich Werte haben. Bei $A=1$ und unbelegtem B gibt es für $A<B$ kein vollständiges Paar, das verworfen werden könnte. Der Versuch $B=1$ scheitert dann sofort. Wartete man, bis jede Variable belegt ist, würde diese einfache Zurückweisung aufgeschoben.

Eine Sackgasse nachvollziehen

Verwende die Workshop-Regeln: $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Nimm die Variablen in der Reihenfolge A, B, C, D, E und versuche die Werte 1, 2, 3.

• Setze $A=1$. Verwirf $B=1$ und wähle $B=2$.
• Verwirf $C=1$ wegen A und $C=2$ wegen B; wähle $C=3$.
• Verwirf $D=1$ wegen A; wähle $D=2$.
• E hat keinen zulässigen Wert: 1 ist verboten, 2 steht mit D und 3 mit C in Konflikt.

Der Fehlschlag bei E führt zu D zurück. Dessen nächster Wert, 3, steht mit C in Konflikt. C hat keinen späteren Wert, daher geht die Suche zu B zurück. Der Versuch $B=3$ führt unter $A=1$ schließlich zu einer weiteren Sackgasse. Die Suche versucht dann $A=2$ und erreicht $A=2,B=3,C=1,D=3,E=2$. In dieser Reihenfolge prüft einfaches Backtracking insgesamt 32 mögliche Werte, einschließlich der verworfenen.

Was das Verfahren garantiert

Auch das Prüfen von Constraints und das Speichern des Modells verursachen Aufwand. Die Angabe zum linearen Speicher betrifft den Suchpfad; Propagation kann zusätzlich Wertebereiche und Änderungsprotokolle speichern.

Chronologisches Backtracking kehrt zur letzten Entscheidung zurück. Schnellere Varianten verbessern vier getrennte Entscheidungen: die nächste Variable, die Reihenfolge ihrer Werte, die nach einer Wahl abgeleiteten Folgen und die frühere Entscheidung, zu der nach einem Fehlschlag zurückgekehrt wird. Diese Verbesserungen verringern den praktischen Aufwand, ohne zu ändern, was als Lösung zählt.

Eine gute Reihenfolge kann einen Fehlschlag weit oben im Suchbaum aufdecken oder brauchbare Wahlmöglichkeiten für später erhalten. Die Reihenfolge der Variablen und die der Werte dienen unterschiedlichen Zwecken; daher erscheint jeweils eine andere Richtung am besten.

Die am stärksten eingeschränkte Variable wählen

Die MRV-Heuristik wählt die unbelegte Variable mit den wenigsten aktuell zulässigen Werten. Sie wird auch Heuristik der am stärksten eingeschränkten Variablen oder Fail-First-Heuristik genannt. Ein nahezu erschöpfter Wertebereich deckt wahrscheinlich bald einen Widerspruch auf. Ist ein Wertebereich leer, scheitert der Zweig sofort.

Zähle die aktuellen Werte nach der Beschneidung, nicht die ursprünglichen Größen der Wertebereiche. Ohne gespeicherte Wertebereiche muss ein Löser vor der Anwendung von MRV bestimmen, welche ursprünglichen Werte noch mit der Belegung konsistent sind.

Die Gradheuristik löst einen Gleichstand bei MRV auf, indem sie die Variable mit den meisten Constraints zu anderen unbelegten Variablen wählt. Eine solche Wahl beeinflusst mehr verbleibende Entscheidungen. Bereits belegte Nachbarn zählen nicht zu diesem verbleibenden Grad. Zu Beginn der Australienkarte liegen die gleich großen Wertebereiche mit drei Farben gleichauf; die fünf Nachbarn von SA geben ihm den höchsten Grad.

Bei der Wertwahl Möglichkeiten offenhalten

Der am wenigsten einschränkende Wert (LCV) wird zuerst versucht: Er entfernt die wenigsten Werte aus den Wertebereichen unbelegter Nachbarn. Die Bewertung möglicher Werte verursacht zusätzlichen Rechenaufwand, kann aber einen aufwendigen gescheiterten Zweig vermeiden.

Bei WA Rot und NT Grün kann SA nur Blau sein, während Q Rot oder Blau sein kann. Die Wahl Q Blau würde den Wertebereich von SA leeren. Die Wahl Q Rot entfernt Rot aus dem Wertebereich von NSW und erhält Blau für SA. LCV versucht daher Q Rot.

Jede Variable muss irgendwann einen Wert erhalten, weshalb die frühe Prüfung einer kritischen Variablen nützlich ist. Um eine erste Lösung zu vervollständigen, wird nur ein Wert benötigt. Das spricht für einen Wert, der Spielraum für andere Entscheidungen lässt.

Reihenfolge mit Forward Checking kombinieren

Wende im Workshop-Zeitplan zuerst $E\mathrm{\ne }1$ an. E hat zwei Werte; A, B, C und D haben jeweils drei. MRV wählt E. Versuche $E=2$, und Forward Checking entfernt 2 aus den Wertebereichen von C und D.

C und D liegen nun mit den Wertebereichen $\{1,3\}$ gleichauf. C hat drei unbelegte Nachbarn, A, B und D; D hat zwei, A und C. Die Gradheuristik wählt C. Wähle $C=1$, wodurch $D_D=\{3\}$ und $D_A=D_B=\{2,3\}$ bleiben. MRV wählt $D=3$, was $A=2$ erzwingt; die Vorrangbedingung ergibt dann $B=3$. Fünf Belegungen führen ohne Backtracking zur Lösung. Eine feste Variablenreihenfolge mit Forward Checking benötigt 12 Belegungen und erreicht zwei Sackgassen.

Die Reihenfolge erhält die Vollständigkeit, weil sie die Abfolge der Entscheidungen ändert, ohne zulässige Zweige zu verwerfen. Der Suchaufwand bleibt im schlimmsten Fall exponentiell. Werden alle Lösungen aufgezählt oder wird Unlösbarkeit bewiesen, müssen schließlich alle relevanten Werte untersucht werden. Daher ist der Vorteil von LCV für einen frühen Erfolg geringer. Der Hauptnutzen liegt darin, eine erste Lösung früher zu finden.

Eine Sackgasse hat oft eine kleinere Ursache als die gesamte aktuelle Belegung. Backjumping nutzt diese Ursache, um zu entscheiden, wohin zurückgekehrt wird, und Constraint-Lernen merkt sich einen Fehlschlag, damit er nicht erneut entdeckt werden muss.

Die Entscheidungen finden, die den Fehlschlag verursacht haben

Nimm auf der Australienkarte die Belegungsreihenfolge Q, NSW, V, T, SA. Q sei Rot, NSW Grün, V Blau und T Rot. SA grenzt an Q, NSW und V, daher sind alle drei Farben verboten. Seine Konfliktmenge ist $\{Q,NSW,V\}$: frühere Variablen, deren gewählte Werte seine Werte ausschließen.

Chronologisches Backtracking würde versuchen, T zu ändern. Tasmanien hat keine Kante zu SA, daher kann eine Änderung seiner Farbe keine Möglichkeit für SA wiederherstellen. Backjumping kehrt zu V zurück, dem zuletzt belegten Mitglied der Konfliktmenge, und überspringt T.

Eine Konfliktmenge enthält Variablen; ein Nogood hält bestimmte Belegungen fest. Dieser Unterschied ist wichtig: Eine andere Farbe für V kann den Fehlschlag beheben, obwohl V weiterhin ein Nachbar von SA ist.

Einen Konflikt durch frühere Fehlschläge weitertragen

Einfaches Backjumping nutzt die direkte Konfliktmenge des aktuellen Fehlschlags. Konfliktgesteuertes Backjumping trägt Informationen durch mehrere gescheiterte Ebenen. Springt eine gescheiterte Variable X zu Y zurück, übernimmt Y die Konfliktmenge von X ohne Y. Sind später alle Werte von Y ausgeschöpft, weist seine vereinigte Menge auf eine weiter zurückliegende Ursache in der Belegung hin.

Verwende zum Beispiel die Reihenfolge WA, NSW, T, NT, Q, V, SA und beginne mit WA Rot, NSW Rot, T Rot. WA und NSW sind keine Nachbarn, daher ist diese partielle Belegung konsistent. Ihre gewählten Werte entfernen Rot aus den Wertebereichen von NT, Q und SA. Diese drei Regionen bilden ein Dreieck, das sich nicht nur mit Grün und Blau färben lässt.

Keine Wahl für T verändert dieses Dreieck. Konfliktinformationen können durch die gescheiterten Versuche zurückgetragen werden und WA und NSW als zugrunde liegende Ursache identifizieren. Die Suche kehrt zu NSW zurück, der späteren dieser beiden Entscheidungen, statt Zeit mit dem Umfärben von T zu verbringen.

Die gescheiterte Kombination lernen

Ein Löser kann $\{WA=\text{Rot},NSW=\text{Rot}\}$ als Nogood festhalten. Wann immer beide Entscheidungen erneut auftreten, folgt derselbe Widerspruch im Dreieck, sodass der Zweig sofort verworfen werden kann. Es wäre falsch, WA Rot für sich allein zu verbieten: WA kann in gültigen Lösungen mit einer anderen Farbe für NSW Rot sein.

Das Lernen fügt einen Constraint oder eine zwischengespeicherte verbotene Kombination hinzu. Die gelernte Bedingung muss aus den ursprünglichen Constraints folgen; ein Fehlschlag allein aufgrund einer erreichten Zeitgrenze liefert keine solche logische Begründung. Ein nützliches Nogood enthält genügend Belegungen, um die Unmöglichkeit zu erklären, ohne unbeteiligte Entscheidungen einzuschließen.

Vorausschau und Rückblick kombinieren

Forward Checking und Kantenkonsistenz entfernen Werte ohne Unterstützung, bevor ein Fehlschlag tief im Baum auftritt. Backjumping untersucht einen Fehlschlag, nachdem er aufgetreten ist. Einfaches direktes Backjumping beschneidet nicht mehr, als Forward Checking bereits erkennt. Konfliktgesteuerte Verfahren können aber Erklärungen tieferer Fehlschläge kombinieren. Lernen erhält diese Erklärungen für spätere Zweige.

Forward Checking prüft, was eine neue Belegung für unbelegte Nachbarn unmittelbar ausschließt. Es entfernt unvereinbare Werte, bevor die Suche diese Variablen erreicht, und macht so manche Sackgassen mehrere Ebenen früher sichtbar.

Nach einer Belegung beschneiden

Untersuche nach der Wahl $X=x$ jede unbelegte Variable Y, die mit X einen Constraint teilt. Entferne jeden Wert aus $D_Y$, der mit der Wahl in Konflikt steht. Ein leerer Wertebereich bedeutet, dass der aktuelle Zweig keine Vervollständigung zulässt. Gehe daher sofort zurück.

Bei $X\mathrm{\ne }Y$ entfernt die Belegung $X=2$ die 2 aus dem Wertebereich von Y. Bei $X<Y$ entfernt $X=2$ jeden Wert von Y, der höchstens 2 ist. Die jeweilige Relation bestimmt, was entfernt wird; Forward Checking ist nicht darauf beschränkt, gleiche Werte zu entfernen.

Die Beschneidung verändert die Wertebereiche des aktuellen Zweigs. Halte jede durch die Wahl verursachte Entfernung in einem Änderungsprotokoll fest. Wird die Wahl rückgängig gemacht, stelle die entfernten Werte wieder her und behalte dabei Einschränkungen aus früheren Entscheidungen bei. Eine andere Implementierung verwendet auf jeder Ebene Kopien der Wertebereiche.

Die Wertebereiche der Workshops verfolgen

Verwende die Zeitfenster 1–3 und die Regeln $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Wende die unäre Regel an, um $D_E=\{2,3\}$ zu erhalten, und verwende dann die feste Reihenfolge A, B, C, D, E.

1. Nach $A=1$ bleibt für B, C und D jeweils $\{2,3\}$.
2. Nach $B=2$ bleibt für C $\{3\}$.
3. Nach $C=3$ bleibt für D und E jeweils $\{2\}$.
4. $D=2$ entfernt 2 aus dem Wertebereich von E und leert ihn. Gehe zurück.

Nach dem Wiederherstellen der Wertebereiche erzwingt der Versuch $B=3$ für C den Wert 2. Für D und E bleibt jeweils 3, sodass die Belegung von D den Wertebereich von E erneut leert. Die Suche muss A ändern. Mit $A=2$ kann sie $B=3,C=1,D=3,E=2$ erreichen. Dieser Ablauf versucht 12 Werte, gegenüber 32 geprüften Kandidaten beim einfachen Backtracking in derselben Reihenfolge.

Die Grenze der Prüfung in einem Schritt erkennen

Nach Schritt 3 haben D und E beide nur den Wert 2 und müssen verschieden sein. Forward Checking hat diesen Constraint noch nicht geprüft: Weder D noch E wurde neu belegt. Es erkennt den Fehlschlag erst, wenn D seinen Wert erhält.

Das ist die zentrale Grenze von Forward Checking. Es prüft die belegte Variable gegen ihre unbelegten Nachbarn, ohne den verkleinerten Wertebereich eines Nachbarn weiterzupropagieren. Kantenkonsistenz kann diese Folgen zwischen unbelegten Variablen verfolgen.

Die aktuell gehaltenen Wertebereiche nutzen

MRV kann nun direkt den kleinsten verbleibenden Wertebereich wählen. Ein Wertebereich mit nur einem Wert wird oft als Nächstes gewählt; ein leerer Wertebereich zeigt einen Fehlschlag an, ohne eine weitere Belegung hinzuzufügen. Aktuelle Wertebereiche helfen sowohl beim Schlussfolgern als auch bei der Reihenfolge.

Bei höchstens $n-1$ Nachbarn und höchstens $d$ Werten pro Nachbar benötigt ein Forward-Checking-Durchlauf etwa $O(nd)$ binäre Prüfungen, sofern eine Relationsprüfung konstante Zeit benötigt. Er entfernt nur Werte, die mit der aktuellen Belegung unvereinbar sind, sodass Backtracking vollständig bleibt. Wird vergessen, einen entfernten Wert wiederherzustellen, kann ein späterer Zweig eine gültige Lösung verlieren; das Beschneiden einer unbeteiligten Variablen kann dasselbe bewirken.

Ein Wert benötigt in jedem benachbarten Wertebereich einen vereinbaren Partner. Kantenkonsistenz macht diese Unterstützungsanforderung ausdrücklich und verfolgt die Auswirkungen von Änderungen der Wertebereiche durch ein binäres CSP.

Unterstützung hat eine Richtung

Knotenkonsistenz entfernt zunächst Werte, die durch unäre Regeln verboten sind. Bei einem binären Constraint ist die gerichtete Kante $X\to Y$ konsistent, wenn jeder Wert von X mindestens einen vereinbaren Wert in Y hat. Dieser Wert in Y ist eine Unterstützung. Die Revision der Kante entfernt Werte ohne Unterstützung aus ihrem Ausgangsknoten X.

Bei $A<B$ mit den Wertebereichen $\{1,2,3\}$ auf beiden Seiten entfernt die Revision von $A\to B$ die 3 aus dem Wertebereich von A. Die Revision von $B\to A$ entfernt die 1 aus dem Wertebereich von B. Die resultierenden Wertebereiche sind $D_A=\{1,2\}$ und $D_B=\{2,3\}$. Ein verbliebener Wert kann für jeden Nachbarn eine andere Unterstützung haben; diese Unterstützungen müssen keine gemeinsame Lösung bilden.

AC-3 ausführen

AC-3 verwendet eine Warteschlange gerichteter Kanten:

1. Lege anfangs jede Kante in die Warteschlange.
2. Entnimm $X\to Y$ und revidiere X mithilfe des Wertebereichs von Y.
3. Wird der Wertebereich von X leer, halte mit einem Fehlschlag an.
4. Schrumpft der Wertebereich von X, füge für jeden anderen Nachbarn Z von X außer Y die Kante $Z\to X$ hinzu.
5. Fahre fort, bis die Warteschlange leer ist.

Eine Entfernung in X kann eine Unterstützung für Z beseitigen, daher muss die Kante in der Warteschlange zurück zum geänderten Wertebereich zeigen. Die Kante von Y muss nicht sofort erneut geprüft werden: Die entfernten Werte von X unterstützten keinen Wert in Y, da keiner von ihnen überhaupt mit Y vereinbar war. Sind die Wertebereiche nach Abschluss nicht leer, hängen sie nicht von der Bearbeitungsreihenfolge ab; bei verschiedenen Reihenfolgen kann ein Fehlschlag jedoch bei verschiedenen leeren Wertebereichen auftreten.

Eine Workshop-Entscheidung propagieren

Bei den Workshop-Regeln $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$ entfernt der anfängliche AC-3-Durchlauf die 3 aus dem Wertebereich von A und die 1 aus dem von B. Für C und D bleibt jeweils $\{1,2,3\}$ und für E $\{2,3\}$.

Entscheide nun $C=1$. Die Kante $A\to C$ entfernt die 1 aus dem Wertebereich von A, sodass $A=2$ bleibt. Die Revision von B anhand von A erzwingt $B=3$. D ist von C und A verschieden, also gilt $D=3$. E ist von D verschieden und kann nicht 1 sein, also gilt $E=2$. Die Verkleinerungen der Wertebereiche haben sich über die unmittelbaren Nachbarn der ursprünglichen Entscheidung hinaus fortgepflanzt.

Die Aufrechterhaltung der Kantenkonsistenz (MAC) wendet diese Schlussfolgerung nach jeder Suchentscheidung an. Ausgehend von kantenkonsistenten Wertebereichen benötigt die Einschränkung auf $X=x$ eine Warteschlange mit eingehenden Kanten von den unbelegten Nachbarn. Entfernte Werte müssen wiederhergestellt werden, wenn die Suche den Zweig rückgängig macht.

Ergebnis und Aufwand deuten

Ein Dreieck mit den Wertebereichen {Rot, Blau} und Ungleichungen auf allen drei Kanten bleibt kantenkonsistent, hat aber keine Lösung. Jede Kante hat für sich Unterstützungen, doch die drei Wahlmöglichkeiten passen nicht zusammen.

Bei $c$ binären Constraints und der maximalen Wertebereichsgröße $d$ benötigt AC-3 $O(c{d}^3)$ Zeit: Eine Kantenrevision prüft bis zu $d^2$ Paare, und jede Kante kann bis zu $d$ Durchläufe benötigen, während ihr Zielknoten Werte verliert. MAC wendet pro Suchknoten mehr auf als Forward Checking und erhält dafür oft einen viel kleineren Suchbaum.

Getrennte paarweise Unterstützungen können einen Widerspruch in einer Gruppe verbergen. Stärkere Konsistenz und spezialisierte globale Propagation untersuchen Kombinationen, die Kantenkonsistenz übersieht, während numerische Schranken große Wertebereiche zu nützlichen Intervallen zusammenfassen können.

Belegungen um eine weitere Variable erweitern

Pfadkonsistenz untersucht Tripel. Jede konsistente Belegung zweier Variablen muss sich um einen Wert für eine dritte erweitern lassen, der mit beiden vereinbar ist. In einem rot oder blau gefärbten Dreieck lassen X Rot und Y Blau keinen Wert für Z übrig. Pfadkonsistenz entfernt dieses erlaubte Paar und deckt schließlich die Unlösbarkeit auf. Sie kann Tupel aus Relationen entfernen und tut damit mehr, als einzelne Werte aus Wertebereichen zu löschen.

k-Konsistenz verlangt, dass sich jede konsistente Belegung beliebiger $k-1$ Variablen um eine beliebige weitere Variable erweitern lässt. Bei binären CSPs entspricht 1-Konsistenz der Knotenkonsistenz, 2-Konsistenz der Kantenkonsistenz und 3-Konsistenz der Pfadkonsistenz. Starke k-Konsistenz umfasst jede Stufe von 1 bis k. Bei starker n-Konsistenz für n Variablen und nicht leeren Wertebereichen lässt sich jede konsistente partielle Belegung ohne Backtracking zu einer Lösung erweitern. Die Herstellung dieser Eigenschaft verursacht im schlimmsten Fall exponentielle Zeit- und Speicherkosten.

Werte in Alldiff zählen

Alldiff verlangt verschiedene Werte für alle Variablen in seinem Geltungsbereich. Hat eine Gruppe von m Variablen nur n verschiedene mögliche Werte und gilt $m>n$, kann keine Belegung den Constraint erfüllen.

Für drei Zellen mit den Wertebereichen $\{4,7\}$ sind die paarweisen Ungleichungen kantenkonsistent: Jede 4 hat in jedem Nachbarn die Unterstützung 7 und jede 7 die Unterstützung 4. Die globale Zählung scheitert dennoch, weil drei verschiedene Werte benötigt werden und nur zwei existieren.

Haben zwei Zellen beide den Wertebereich $\{4,7\}$, müssen sie untereinander 4 und 7 verwenden. Diese Werte können aus allen anderen Zellen derselben Zeile entfernt werden. Diese Schlussfolgerung mit einem nackten Paar nutzt eine Teilmenge des gesamten Alldiff-Geltungsbereichs. Ein einfacher globaler Propagator kann auch wiederholt Variablen mit nur einem Wert verarbeiten, deren Werte an anderer Stelle entfernen und prüfen, ob zu wenige verschiedene Werte übrig bleiben. Stärkere Propagatoren erkennen auch eingeschränkte Teilmengen.

Numerische Schranken verschärfen

Schrankenpropagation speichert einen Wertebereich anhand seines Minimums und Maximums. Schrankenkonsistenz verlangt, dass jeder Endpunkt für jeden relevanten Constraint eine erfüllende Erweiterung hat; sie prüft nicht jeden inneren Wert.

Für zwei Busse, die 100 Personen befördern, sei $B_1\in [0;50]$ und $B_2\in [0;70]$, wobei $B_1+B_2=100$ gilt. Der zweite Bus befördert höchstens 70 Personen, was $B_1\ge 30$ erzwingt. Der erste befördert höchstens 50, was $B_2\ge 50$ erzwingt. Die verschärften Intervalle sind $[30;50]$ und $[50;70]$.

Für Vorbereiten, Analysieren und Bericht erstellen mit einer Dauer von 20, 40 und 30 Minuten in dieser Reihenfolge ergeben sich bei einer Frist von 120 Minuten die spätesten Startzeiten 30, 50 und 90. Nichtnegative Startzeiten ergeben die frühesten Startzeiten 0, 20 und 60. Durch Propagation vorwärts und rückwärts erhält man diese Zeitfenster, bevor eine Startzeit gewählt wird.

Eine geeignete Stärke wählen

Jede Sudoku-Zelle hat 20 verschiedene andere Zellen mit gemeinsamem Constraint: 8 in ihrer Zeile, 8 in ihrer Spalte und 4 zusätzliche Zellen in ihrer Box. Über 81 Zellen hinweg ergibt das $81\times 20\mathrm{/}2=810$ verschiedene ungleiche Paare. Globale Constraints erhalten dieselben Lösungen wie diese Paare, können aber nackte Paare und einen Mangel an Werten früher aufdecken. Stärkeres Schlussfolgern kostet pro Durchlauf mehr; praktische Löser wägen diesen Aufwand gegen die eingesparte Suche ab und kombinieren häufig Kantenkonsistenz mit spezialisierter globaler Propagation und Schrankenpropagation.

Lokale Suche beginnt mit einem Wert für jede Variable, auch wenn einige Constraints verletzt sind. Die Min-Konflikte-Heuristik repariert diese vollständige Belegung, indem sie einer konfliktbehafteten Variablen einen Wert mit möglichst wenigen Konflikten zuweist.

Eine Reparatur wählen

1. Erstelle eine vollständige Belegung, zufällig oder durch gierige Auswahl.
2. Wird kein Constraint verletzt, gib die Lösung zurück.
3. Wähle zufällig eine Variable, die an einem verletzten Constraint beteiligt ist.
4. Bewerte jeden Wert ihres Wertebereichs gegenüber den anderen Variablen, die fest bleiben.
5. Wähle einen Wert mit den wenigsten Konflikten, löse Gleichstände zufällig auf und wiederhole das Verfahren bis zum Erfolg oder bis zu einer Schrittgrenze.

Eine konfliktbehaftete Variable ist an mindestens einem verletzten Constraint beteiligt. Sie ist nicht notwendigerweise die Variable mit den meisten Verletzungen. Die zufällige Wahl unter konfliktbehafteten Variablen und gleich guten Werten hilft, eine starre wiederholte Abfolge zu vermeiden.

Ein Brett für das 4-Damen-Problem reparieren

Verwende eine Dame pro Spalte mit den Zeilenvariablen $Q_1,Q_2,Q_3,Q_4$. Ein Paar steht in Konflikt, wenn die Zeilen gleich sind oder der Zeilenabstand dem Spaltenabstand entspricht. Beginne mit $(2,4,2,3)$. Die Spalten 1 und 3 teilen sich Zeile 2; die Damen in den Spalten 3 und 4 greifen sich diagonal an. Die konfliktbehafteten Variablen sind Q1, Q3 und Q4.

Wähle Q3 und bewerte die Zeilen, während Q1, Q2 und Q4 fest bleiben:

Zeile 1 ergibt $(2,4,1,3)$, eine Lösung. Wäre stattdessen Q1 gewählt worden, wären seine Konfliktzahlen für die Zeilen 1–4 gleich 0, 1, 2 und 2. Ein Zug in Zeile 1 ergibt $(1,4,2,3)$, wobei der diagonale Konflikt zwischen Q3 und Q4 bleibt. Auch nach einer lokal besten Reparatur können also weitere Reparaturen nötig sein.

Zähle die Constraints, an denen die gewählte Variable beteiligt ist. Zählt man alle Verletzungen auf jedem entstehenden Brett, ergibt sich dieselbe Reihenfolge, weil unbeteiligte Constraints zu jedem Kandidaten einen konstanten Beitrag leisten. Das erfordert lediglich mehr Aufwand. Verwende beim Vergleich der Kandidaten eine einheitliche Definition von Konflikten.

Einen bestehenden Zeitplan reparieren

Fällt eine Lehrkraft aus, ist der aktuelle Zeitplan bereits eine vollständige Belegung. Die Min-Konflikte-Heuristik kann dort beginnen und Veranstaltungen verschieben, bis die neuen und bestehenden Constraints erfüllt sind. Eine kleine Änderung benötigt oft wenige Reparaturen, obwohl ein Schritt anderswo neue Konflikte erzeugen kann. Ist es wichtig, den alten Plan beizubehalten, weise der Änderung einer Belegung explizite Kosten zu; allein die Minimierung von Verletzungen minimiert nicht die Änderungen am Plan.

Experimente mit einer guten Anfangsbelegung benötigten selbst für eine Million Damen relativ wenige Reparaturschritte. Größere Bretter machen jeden Schritt dennoch aufwendiger. Die Min-Konflikte-Heuristik wurde auch für die Hubble-Planung eingesetzt; Berichten zufolge verkürzte sich die Planung einer Woche von Beobachtungen von etwa drei Wochen auf etwa 10 Minuten.

Das Suchverhalten deuten

Viele Familien zufälliger CSPs gehen von überwiegend lösbar zu überwiegend unlösbar über, wenn das Verhältnis von Constraints zu Variablen steigt. In der Nähe dieses Übergangs ist die Entscheidung, wie Wahlmöglichkeiten zusammenwirken, oft am schwierigsten. Probleme mit wenigen Einschränkungen können viele leicht erreichbare Lösungen haben. Stark eingeschränkte unlösbare Probleme können von vollständigen Lösern mit Propagation schnell als unlösbar erkannt werden.

Das Erreichen einer Schrittgrenze bei der Min-Konflikte-Heuristik bedeutet, dass in diesem Durchlauf keine Lösung gefunden wurde. Das Problem kann dennoch lösbar sein. Die praktische Stärke des Verfahrens liegt in effizienten Reparaturen, einschließlich Schritten zu gleich bewerteten Zuständen, obwohl Lösungen nur einen winzigen Anteil aller möglichen Belegungen ausmachen.

Eine Reparatursuche kann aufhören, sich zu verbessern, obwohl Konflikte bestehen bleiben. Um weiterzukommen, benötigt der Löser eine Möglichkeit, sich durch gleich bewertete Zustände zu bewegen oder zu ändern, welche Schritte lohnend erscheinen. Auch das benötigte Ergebnis zählt: Eine schnelle zulässige Reparatur und ein Beweis der Unlösbarkeit verlangen unterschiedliche Verfahren.

Ein Plateau durchqueren

Ein lokales Minimum hat Verletzungen, aber keine Änderung einer einzelnen Variablen, die deren Anzahl senkt. Ein Plateau ist ein zusammenhängender Bereich von Belegungen mit gleicher Bewertung. Schritte, die nur bergab führen, können stecken bleiben; ein Seitwärtsschritt verändert den Zustand, ohne die Bewertung zu senken.

Beim 4-Damen-Problem hat $(1,4,2,3)$ einen Konflikt zwischen Q3 und Q4. Bei festgehaltenen anderen Damen sind die Konfliktzahlen von Q3 für die Zeilen 1–4 gleich 1, 1, 3 und 2; die von Q4 sind 2, 2, 1 und 2. Keine der beiden Variablen hat einen verbessernden Zug.

Ein Zug von Q3 in Zeile 1 ergibt $(1,4,1,3)$, weiterhin mit einem Konflikt: Nun stehen Q1 und Q3 in derselben Zeile. In diesem neuen Zustand sind die Konfliktzahlen von Q1 gleich 1, 0, 3 und 1. Ein Zug von Q1 in Zeile 2 ergibt $(2,4,1,3)$ und beseitigt den Konflikt. Der Seitwärtsschritt hat verändert, welche verbessernden Züge verfügbar waren.

Die Suche in Bewegung halten

Eine Tabuliste ist ein kurzlebiges Gedächtnis. Sie erschwert die sofortige Rückkehr zu einem gerade verlassenen Zustand. Ein Neustart erkundet einen anderen Bereich, während die simulierte Abkühlung innerhalb des aktuellen Durchlaufs einen Bereich mit mehr Konflikten überqueren kann.

Beginne bei der Constraint-Gewichtung jedes Gewicht bei 1 und bewerte einen Zustand anhand der Summe der Gewichte seiner verletzten Constraints. Wähle eine Änderung, die diese gewichtete Bewertung senkt, und erhöhe dann die Gewichte der weiterhin verletzten Constraints. Wiederholte Fehlschläge werden teurer und verändern die Suchlandschaft. Eine gewichtete Bewertung von null bedeutet weiterhin, dass jeder positiv gewichtete harte Constraint erfüllt ist.

Den benötigten Nachweis wählen

Lokale Suche ist unvollständig: Sie kann eine existierende Lösung übersehen, und ein endlicher erfolgloser Durchlauf lässt die Frage der Unlösbarkeit offen. Backtracking mit Propagation bei endlichen Wertebereichen ist vollständig: Es findet schließlich eine Lösung oder schöpft jede mögliche Vervollständigung aus.

Verwende lokale Suche, wenn ein großes Problem mit wenigen Einschränkungen eine zulässige Belegung oder eine schnelle Reparatur benötigt. Backtracking mit MRV und MAC ist eine gute Wahl für stark eingeschränkte Rätsel und immer dann, wenn die Aufgabe den Nachweis der Unlösbarkeit verlangt. Die Laufzeit hängt weiterhin vom jeweiligen Problemfall ab; diese Verfahrensentscheidungen beruhen auf den jeweiligen Garantien.

Der Workshop-Zeitplan hat die eindeutige Lösung $A=2,B=3,C=1,D=3,E=2$. Das Hinzufügen von $C\mathrm{\ne }1$ schließt sie aus. Die Min-Konflikte-Heuristik kann bis zu ihrer Grenze Reparaturen versuchen, doch erst eine vollständige Suche, die die verbleibenden Fälle ausschöpft, stellt fest, dass die organisierende Person eine Anforderung ändern muss, etwa indem sie ein weiteres Zeitfenster hinzufügt.

Ein Constraint-Graph kann kleinere Probleme innerhalb eines großen sichtbar machen. Unabhängige Komponenten lassen sich getrennt lösen, und für azyklische Komponenten gibt es einen besonders effizienten Algorithmus mit einem beschneidenden Rückwärtsdurchlauf und einem belegenden Vorwärtsdurchlauf.

Getrennte Komponenten zerlegen

Eine Zusammenhangskomponente ist unabhängig, wenn kein Constraint ihre Variablen mit einer anderen Komponente verbindet. Löse jede Komponente und kombiniere dann je eine Lösung aus jeder. Ist eine Komponente unlösbar, ist das gesamte CSP unlösbar. Auf der Australienkarte ist Tasmanien unabhängig vom Festland.

Sind n Variablen in unabhängige Gruppen der Größe c aufgeteilt, liegt der Aufwand, eine vollständige Belegung zu finden, bei $O((n\mathrm{/}c)d^c)$ statt bei $O(d^n)$. Für 60 binäre Variablen, aufgeteilt in drei Gruppen zu je 20, betrachten getrennte erschöpfende Suchen höchstens $3\times 2^{20}=\mathrm{3.145.728}$ Belegungen statt etwa $\mathrm{1,15}\times {10}^{18}$. Um jede kombinierte Lösung aufzuzählen, müssten weiterhin die Kombinationen aufgelistet werden; die Einsparung beschreibt das Lösen der Teilprobleme.

Einen Baum von seiner Wurzel aus ordnen

Ein binäres CSP ist baumstrukturiert, wenn sein Constraint-Graph azyklisch ist. Ein zusammenhängender Baum hat zwischen jedem Variablenpaar einen Pfad; ein Wald enthält getrennte Bäume. Wende zuerst unäre Einschränkungen an. Wähle eine beliebige Wurzel und ordne die Variablen so, dass jeder Elternknoten vor seinen Kindern erscheint.

Gerichtete Kantenkonsistenz in dieser Reihenfolge verlangt, dass jede frühere Variable in jedem späteren Nachbarn Unterstützung hat. In einem Baum sind diese späteren Nachbarn ihre Kinder. Die Richtung der Unterstützung führt vom Elternknoten zum Kind, obwohl der Algorithmus Kinder vor Elternknoten verarbeitet.

Rückwärts beschneiden, vorwärts belegen

1. Lies die Reihenfolge rückwärts, ohne die Wurzel. Revidiere für jedes Kind die Kante von seinem Elternknoten zu diesem Kind. Entferne Werte ohne Unterstützung aus dem Wertebereich des Elternknotens.
2. Wird ein Wertebereich leer, melde, dass es keine Lösung gibt.
3. Lies die Reihenfolge vorwärts. Wähle einen beliebigen verbliebenen Wert für die Wurzel und gib dann jedem Kind einen Wert, der mit seinem belegten Elternknoten vereinbar ist.

Die Nachkommen des Kindes wurden bereits verarbeitet, wenn sein Elternknoten revidiert wird. Ein verbliebener Wert des Elternknotens hat daher in jedem Kind Unterstützung, und jeder Wert eines Kindes hat bereits weiter unten Unterstützung. Verschiedene Kindzweige sind nicht durch Kanten verbunden, sodass diese Unterstützungen unabhängig gewählt werden können. Deshalb benötigt der Vorwärtsdurchlauf kein Backtracking.

Den Workshop-Baum verfolgen

Lege im Workshop-Zeitplan $C=1$ fest und entferne 1 aus den Wertebereichen der anderen Workshops. Der verbleibende Graph ist der Pfad B–A–D–E mit den Wertebereichen $\{2,3\}$ und den Constraints $A<B,A\mathrm{\ne }D,D\mathrm{\ne }E$.

Wähle die Wurzel A und die Reihenfolge A, B, D, E. Der Rückwärtsdurchlauf revidiert $D\to E$ und dann $A\to D$ ohne Änderungen. Schließlich entfernt $A\to B$ die 3 aus dem Wertebereich von A, weil B keinen größeren Wert hat. Die Vorwärtsbelegung ergibt $A=2,B=3,D=3,E=2$. Nimmt man $C=1$ wieder hinzu, ergibt sich der vollständige Zeitplan.

Für n Variablen mit maximaler Wertebereichsgröße d revidiert der Rückwärtsdurchlauf $n-1$ Kanten mit jeweils bis zu $O(d^2)$ Aufwand. Das ergibt $O(n{d}^2)$ Zeit. Die Garantie hängt von der Zyklenfreiheit ab. Ein Zyklus kann getrennte Kindzweige verbinden und die Unabhängigkeit aufheben, die diese lokalen Entscheidungen sicher gemacht hat.

Ein Graph mit wenigen Zyklen kann einem Baum dennoch ähnlich genug sein, um effizient gelöst zu werden. Die Schnittmengenkonditionierung belegt zuerst ausgewählte Variablen; die Baumzerlegung fasst Variablen zu überlappenden Teilen zusammen. Beide machen die verbleibende Abstimmung baumförmig.

Auf eine Zyklenschnittmenge konditionieren

Eine Zyklenschnittmenge ist eine Menge von Variablen, deren Entfernung einen Baum oder Wald übrig lässt. Prüfe jeden verbleibenden Zyklus, nicht nur den auffälligsten. Auf der Australienkarte bleiben nach Entfernung von SA der Pfad WA–NT–Q–NSW–V und das isolierte T. Beim Workshop-Graphen bleibt nach Entfernung von C der Pfad B–A–D–E.

Für jede Belegung der Schnittmenge, die deren interne Constraints erfüllt:

1. Entferne unvereinbare Werte aus den verbleibenden Wertebereichen.
2. Löse jeden verbleibenden Baum durch Rückwärtsbeschneidung und Vorwärtsbelegung.
3. Sind alle erfolgreich, kombiniere ihre Belegungen mit den Werten der Schnittmenge. Versuche andernfalls eine andere Belegung der Schnittmenge.

Im Workshop-Problem lässt $C=1$ einen lösbaren Baum übrig. Bei $C=2$ müssen A und B aus $\{1,3\}$ stammen und $A<B$ erzwingt $A=1,B=3$. D muss sowohl von A als auch von C verschieden sein, was $D=3$ ergibt. E kann nicht 1 sein und muss von C und D verschieden sein, sodass kein Wert bleibt. Bei $C=3$ müssen A und B die Werte 1 und 2 haben; D muss dann 2 sein, wodurch erneut kein Wert für E bleibt.

Bei Schnittmengengröße c gibt es höchstens $d^c$ Belegungen, auf die jeweils ein Baumproblem mit dem Aufwand $O((n-c)d^2)$ folgt. Insgesamt ergibt das $O(d^c(n-c)d^2)$. Ein kleines c macht dies nützlich; der Aufwand bleibt exponentiell in c. Eine minimale Schnittmenge zu finden ist NP-schwer, aber auch eine gültige, nicht minimale Schnittmenge ergibt ein korrektes Verfahren.

Überlappende Mengen verbinden

Eine Baumzerlegung ordnet Variablenmengen, sogenannte Taschen, in einem Baum an. Sie muss drei Bedingungen erfüllen:

• Jede Variable erscheint in einer Tasche.
• Der Geltungsbereich jedes Constraints passt in mindestens eine Tasche.
• Die Taschen, die eine bestimmte Variable enthalten, bilden einen zusammenhängenden Teil des Taschenbaums.

Die dritte Regel ist die Running-Intersection-Eigenschaft. Erscheint X an beiden Enden eines Taschenpfads, muss es auf dem gesamten Pfad erscheinen. Andernfalls könnten entfernte Taschen inkonsistente Werte für X wählen, ohne dass eine dazwischenliegende Übereinstimmungsprüfung stattfindet.

Die lokal gültigen Belegungen jeder Tasche werden zu Werten einer Mega-Variablen. Benachbarte Taschen müssen bei gemeinsamen Variablen übereinstimmen. Der resultierende Baum koordiniert die lokalen Lösungen. Für ein Dreieck X–Y–Z–X mit zusätzlicher Kante Z–W decken die Taschen $\{X,Y,Z\}$ und $\{Z,W\}$ jede Kante ab und stimmen bei Z überein.

Die Baumweite der Zerlegung ist ihre größte Taschengröße minus 1. Die Baumweite eines Graphen ist das Minimum über gültige Zerlegungen. Für die Weite w lautet die Standardschranke für CSPs $O(n{d}^{w+1})$. Eine feste beschränkte Weite begrenzt den Exponenten.

Wertesymmetrie entfernen

Haben Farbnamen keine besondere Bedeutung, erhält eine Vertauschung von Rot, Grün und Blau die Gültigkeit. Die sechs Lösungen für das australische Festland sind sechs Umbenennungen eines Musters. Legt man die Reihenfolge NT vor SA vor WA in der Farbreihenfolge Rot, Grün, Blau fest, bleibt ein Repräsentant übrig. Ein solcher symmetriebrechender Constraint ist nur zulässig, wenn die Umbenennung die ursprünglichen Regeln erhält. Eine Regel, die für eine bestimmte Region Rot verlangt, macht diese Farbe besonders und verändert, welche Vertauschungen Symmetrien bleiben.