Struktur- und Konsistenzeigenschaften von Constraint-Satisfaction-Problems (CSPs)

Kurzbeschreibung

Inhalt

5 Quellen

1 Einleitung

Zum Beispiel soll für die Erstellung einer Landkarte sichergestellt werden, daß angrenzende Länder verschieden eingefärbt sind, um sie besser unterscheiden zu können. In Bild 1 ist ein Beispiel einer solchen Landkarte zu sehen. Die Sechsecke stellen die Länder dar, die A, B und C heißen. Jedes Land  wird durch eine Variable repräsentiert und soll eine andere Farbe besitzen als sein Nachbar. Eine gewisse Anzahl von Farben stehen jedem Land zur Verfügung, so z.B. kann B die Farben a und b oder C nur die Farbe c annehmen. Das zu erfüllende Constraint lautet: >>Ein Land darf nicht die gleiche Farbe haben wie eines seiner Nachbarländer.<<

Bei der Lösung eines CSP wird nun durch Reduktion der Domänen versucht, die Variablenbelegungen, die eine Verletzung der Constraints verursachen würden, auszuschließen. Dazu wird eine Variable mit einem Wert belegt und die Werte der Variablen, die mit dieser durch Constraints verbunden sind, überprüft. Bei dieser Überprüfung werden die Werte aus den Domänen genommen, die eine Verletzung der Constraints verursachen würden. Es findet also eine Suche über die möglichen Wertebelegungen der Variablen statt. Eine solche Suche kann im allgemeinen durch einen Suchbaum repräsentiert werden. Jede Variable wird durch eine Ebene in diesem Suchbaum repräsentiert.

Die Suche erfolgt ausgehend von der Wurzel des Baumes. Sellt sich zu einem Zeitpunkt der Suche heraus, daß diese unter den gegenwärtigen Variablenbelegungen nicht erfolgreich beendet werden kann, so muß in dem Suchbaum wieder eine Ebene nach oben gegangen werden. Dies wird Backtracking genannt.

In Bild 2 ist ein Suchbaum zu sehen. Ein Pfad wird bis zu einem Blatt verfolgt, ohne Rücksicht darauf zu nehmen, daß bereits vor einer vollständigen Belegung ein Fehler entdeckt werden könnte. Backtracking erfolgt, wenn sich in dem Pfad keine Lösung befindet. Der Vorgang wird solange wiederholt, bis eine Lösung gefunden wird.

Dazu werden zu Beginn die für das Verstehen dieses Dokuments wichtigen Begriffe beschrieben. Zur Verdeutlichung dient im wesentlichen das Beispiel mit der Landkarte.

Der erste Schritt wird sein, den Begriff "Constraint" zu erklären und damit zusammenhängende Begriffe einzuführen. Dann wird im zweiten Kapitel auf die verschiedenen Möglichkeiten eingegangen, die es erlauben, durch Constraints miteinander verbundene Variablen auf ihre Gültigkeitsbereiche zu prüfen und gegebenenfalls deren Wertebereiche einzuschränken. Im dritten Kapitel wird dann vorgestellt, wie man die Struktur, die hinter einem Problem steht, benutzen kann, um effizient nach Lösungen für dieses Problem zu suchen. Dabei werden verschiedene Arten der Darstellung eines Problems erläutert bzw. angedeutet.

In Bild 3 ist das Problem zum automatischen Erkennen von geometrischen Formen abgebildet. Zu einer Ecke (einem Knoten) dürfen nicht mehr als drei Kanten gehen. Daraus ergeben sich vier verschiedene Knotentypen mit jeweils unterschiedlichen Belegungen der entsprechenden Kanten. Ziel ist es, eine  eindeutige Belegung für die Knoten zu finden, so daß sich an den Enden einer verbindenden Kante zweier Knoten immer die gleichen Symbole befinden.
Wenn in den folgenden Beispielen für die Belegung eines Knotens eine Zahl angegeben ist, dann ist der Knoten mit der entsprechenden Numerierung gemeint. Des weiteren sollen die Domänen der Knoten (Variablen) auf die angegebenen Belegungen beschränkt sein, da sonst die Beispiele zu unhandlich wären. [FRE82].

1.1 Was sind Constraints?

Constraints lassen sich in drei Kategorien einteilen: unäre Constraints, binäre Constraints und n-äre Constraints.

Die unären Constraints sind solche, die sich nur auf eine Variable beziehen, d.h., daß sie z.B. den Wertebereich einer Variablen explizit einschränken. In dem Beispiel in Bild 3 könnte ein unäres Constraint beispielsweise alle Werte außer c der Variablen C ausschließen (wie bereits geschehen).

Die binären Constraints beziehen sich immer auf zwei Variablen, so wie in dem Beispiel des Constraint-Coloring-Problems das Constraint >>nicht die gleiche Farbe<<. Hier lassen sich durch Belegung der einen Variablen die gültigen Werte der zweiten Variablen einfach ermitteln.

Die n-ären Constraints stellen mehr als zwei Variablen miteinander in Beziehung, z.B. "A + B = C". Die meisten Algorithmen der Constraint-Programmierung basieren allerdings auf einer Repräsentation des Problems mit maximal binären Constraints. Es wurden deshalb Verfahren entwickelt, n-äre Constraints auf binäre Constraints zurückzuführen.

1.2 Was ist Constraint-Programmierung?

Die Constraint-Programmierung stellt Verfahren zur Verfügung, mit denen sich CSPs effizient lösen lassen. Dabei ist zu beachten, daß das Lösen von CSPs nicht in polynomialer Zeit möglich ist, also NP-Vollständig ist. Mit Hilfe der Auswertung der Struktur des zu lösenden CSP kann aber oft ein relativ effizienter Algorithmus gefunden werden. Bei einfachen Strukturen (Bäumen) geht es sogar so weit, daß ein Suchbaum für die Werte der Variablen aufgestellt werden kann, in dem nur Lösungen enthalten sind, die alle Constraints erfüllen. In einem solchen Fall ist es ohne Backtracking möglich, eine global konsistente Lösung für die Variablen bzgl. der Constraints aus dem Baum auszulesen.

Das Überprüfen von Constraints bei einer bestimmten Belegung der Variablen wird auch als Constraint-Check bezeichnet.

2 Konsistenz

Für die Constraintchecks gibt es verschiedene Verfahren, um konsistente Lösungen zu finden, bzw. inkonsistente Lösungen möglichst früh zu erkennen und zu verwerfen. Auf diese Weise kann der Suchaufwand nach einer global konsistenten Lösung in vielen Fällen erheblich eingeschränkt werden. [FRE82].

2.1 Node-Consistency

2.2 Arc-Consistency

Es gibt verschiedene Verfahren eine Arc-Consistency zu erreichen. Ein möglicher Algorithmus ist der AC-3. Entnommen aus [BAR98].

Prozedur zum Löschen eines Wertes aus einer Domain, wenn keine Konsistenz erreicht werden kann:

procedure REVISE (V_i,V_j)
  DELETE <- false;
  for each X in D_i do
    if there is no such Y in D_j such that (X,Y) is consistent,
    then
      delete X from D_i;
      DELETE <- true;
    endif;
  endfor;
  return DELETE;
end REVISE
 

procedure AC-3
  Q <- {(V_i,V_j) in arcs (G), i # j};
  while not Q empty
    select and delete any arc (V_k,V_m) from Q;
    if REVISE (V_k,V_m) then
      Q <- Q union {(V_i,V_k) such that (V_i,V_k) in arcs (G), i # k, i # m}
    endif
  endwhile
end AC-3

Zuerst wird die Menge Q aller Kanten zwischen den Knoten gebildet (der Constraint-Graph für das Beispiel ist in Bild 5 zu sehen). Dabei ist zu beachten, daß der Algorithmus die Kante (V_i, V_j) von der Kante (V_j, V_i) unterscheidet. Die Menge Q aller Kanten für den Graphen sieht also folgendermaßen aus:

  Q = { (B, A), (B, E), (B, C),
        (C, B), (C, D), (C, E),
        (D, A), (D, C),
        (E, B), (E, C),
        (A, B), (A, D) }

2.3 K-Consistency

Path-Consistency kann auf ähnliche Weise wie Arc-Consistency erreicht werden. Zuerst wird für einen Knoten Arc-Consistency erreicht. Dann wird zu zwei Nachbarn jeweils ein konsistentes Wertpaar gesucht, so daß die Belegung der untersuchten Variablen identisch ist. Kann dies nicht erreicht werden, so werden die entsprechenden Wertepaare aus der Lösungsmenge für das entsprechende binäre Constraint gelöscht. [BAR98].

3 Strukturen

Das Ziel von allen Methoden ist die Neuanordnung des Problems, so daß die Suche nach einer Lösung in den neu geschaffenen Bäumen so einfach wie möglich wird. Unter Neuanordnung eines Graphen ist die äquivalente Umformung des Graphen zu verstehen. Der einfachste Fall ist genau dann erreicht, wenn die Traversierung des Suchbaumes eine Suche ohne Backtracking ermöglicht.

Als Vorlage für die Strukturen in Bild 6 dient die in Kapitel 1 vorgestellte Figur (Erkennung von geometrischen Figuren). Die Knoten A bis E von der geometrischen Figur werden auf die Variablen A bis E in den Graphen abgebildet.

CSPs lassen sich unter drei Gesichtspunkten betrachten:

Makro-Struktur:
Die Probleme können als Constraint-Graphen dargestellt werden (siehe Bild 6a). Variablen werden auf die Knoten abgebildet und die Constraints zwischen den Variablen auf Kanten der entsprechenden Knoten. Die originalen Constraints dürfen nicht verändert werden. Bei der Spezifikation eines Constraints werden die konsistenten Variablenbelegungen (bei uns Wertepaare) in einer Menge dargestellt.

Meta-Struktur:
Hier wird das Ausgangsproblem in Teilprobleme (Metaprobleme) zerlegt, um es in ein Problem mit einer vereinfachten Makro-Struktur zu überführen. Die neu gewonnenen Meta-CSPs können in einem Metaconstraint-Graphen dargestellt werden (siehe Bild 6b, Ausgangsproblem siehe Bild 6a). Die Variablen eines Teilproblems werden in einer Metavariable zusammengefaßt. Dabei sind die Metavariablen des Metaproblems mit den Teilproblemen des Ausgangsproblems gleichzusetzen. Jedes Teilproblem besteht aus einer Teilmenge der Variablen mit den jeweiligen Domänen und Constraints. Die Menge der Metawerte einer Metavariable entspricht der Menge der Lösungen für das Teilproblem. Durch die Belegung der ersten Metavariablen mit einem Wert, wird automatisch die Domäne einer Variablen in der zweiten Metavariablen eingeschränkt (nämlich die, die in beiden Metaproblemen vorkommt). Es müssen nun für die anderen Variablen nur noch konsistente Lösungen zu der fixierten gefunden werden. Diese Konstruktion mit der fixierten Variable wird Metaconstraint genannt.

Mikro-Struktur:
Mit Paaren von konsistenten Werten arbeitet die Mikro-Struktur, die in einem Consistency-Graph dargestellt werden (siehe Bild 6c). Das Ziel ist es, den Suchraum vorab zu verkleinern. Dabei sind die Knoten die Repräsentanten von Werten und die Kanten stellen ein Paar von konsistenten Werten dar.

3.1 Makro-Strukturen

3.1.1 Zyklenfreie CSP-Graphen

Der Directed-Constraint-Graph (und dessen Anordnung der Variablen) besitzt die Breite 1. Die Breite 0 hat ein Graph, in dem es keine Kanten gibt; gibt es einen Knoten in einem Directed-Constraint-Graphen mit mindestens 2 Vorgängern, so hat der Graph die Breite 2. Hat der Graph die Breite 1 und es wird ein zulässiger Wert für eine Variable ausgesucht, so muß nur die Konsistenz der Variablen zum Vorgänger garantiert werden.  Es wird Arc-Consistency hergestellt. [SHA93].

Durch sie wird der Suchbaum stark reduziert und es wird garantiert, daß immer in der nächsten Ebene des Suchbaums ein konsistenter Wert gefunden wird. Bei Nichtkonsistenz wird der gesamte Unterbaum gelöscht. Eine Backtrack-Free-Search entsteht.

Hier sind noch einmal die drei Schritte zur Lösung eines CSPs mit zyklenfreien Graphen:

• Erstelle einen Directed-Constraint-Graph mit der Breite 1,
• erreiche Arc-Consistency und
• führe eine Backtrack-Free-Search aus.

An dem Beispiel in Bild 7 (Einfärbung von Landkarten) soll ausgeführt werden, wie die Umwandlung von einem zyklenfreien Constraint-Graphen in ein Arc-Consistent-Ordered-Constraint-Graphen (ACOCG) abläuft: Zuerst wird eine Kopie des CG erstellt. Man nehme immer vom CG den Knoten mit den meisten Kanten und lösche den Knoten (B). Der erste gelöschte Knoten ist im ACOCG die Wurzel. Besitzt eine Kante keinen Knoten mehr, so wird sie gelöscht (die Kanten AB, BC und BD). Haben zwei oder mehrere Knoten die gleiche Anzahl von Kanten, dann ist es egal, welcher Knoten als erstes verwendet wird (eine Kante für A und E und keine Kante für C und D). Zum Schluß werden alle Constraints im CG auf den ACOCG übertragen.

B hat die meisten Kanten (drei) und wird zur Wurzel im ACOCG. Nach B folgt A (oder E) mit einer Kante und damit die Anordnung von A unter B. C, D und E haben jetzt jeweils nur eine Kante. Die Reihenfolge der Knoten C, D und E ist damit beliebig. Entstanden ist ein Graph mit der Breite 1. Jeder Knoten hat genau einen Vorgänger.

Im Knoten A vom linken Graphen im Bild 7 entfällt nach der Arc-Consistency-Prüfung der Wert rot, da für die Variable E kein konsistenter Wert gefunden kann.

Ohne Backtracking können nun Lösungen aus dem resultierenden Suchbaum des ACOCG direkt abgelesen werden, z. B. (rt, gn, rt, bl, gb).

3.1.2 CSP-Graphen mit Zyklen

Gestartet wird eine K-Baum Erzeugung mit einer Gruppe von k Knoten, z. B. eine Menge k Knoten von denen einige über eine Kante miteinander verbunden sind. Danach werden die übrigen Knoten durch Verbindungen an die bereits bestehende Gruppe angefügt. K+1-Consistency entsteht, wenn alle gegebenen Werte aller k Variablen gegenseitig konsistent sind und darüber hinaus ein Wert für jede K+1 Variable gefunden werden kann, die zu allen anderen Werten der anderen Variablen konsistent ist. Eine Directed-K+1-Consistency ist eine K+1-Consistency mit weiteren Einschränkungen. Es müssen nur die Werte der k Variablen benutzt werden, durch deren Hilfe man einen Wert für eine K+1 Variable finden kann. Eine starke Directed-K+1-Consistency kann durch die Entfernung von Werten einer Variablen erreicht werden, bei der keine Konsistenz zu den vorhergehenden Variablen im Graph erreichbar ist.
Eine Strong-K+1-Consistency ist eine J-Consistency für alle J <= K.

Directed K+1 -Consistency  stellt Konsistenz in einem Teilbaum sicher. Eine Umordnung der Knoten in diesem Teilbaum zerstört nicht die Konsistenz, da zu jedem Wert eines Knotens wiederrum eine K+1-Consistency existiert.

Die Schritte zur Sicherstellung einer Backtrack-Free-Search sind:

• Finde eine Variablenanordnung mit der Breite k,
• erreiche eine Directed-K+1-Consistency und
• führe eine Backtrack-Free-Search aus.

Im Bild 8 ist ein Beispiel für die Umwandlung von einem Constraint-Graphen in einen Path-Consistent-Ordered-Graphen zu sehen (Erkennung von geometrischen Figuren). Die maximale Anzahl von Vorgängern von einem Knoten beträgt zwei. B bildet wegen seiner 3 Kanten die Wurzel. A, C und D haben jeweils 2 Kanten, können also in beliebiger Reihenfolge in dem neuen Graphen eingeordnet werden. E ist der letzte Knoten mit nur einer Kante und wird ans Ende des Graphen gehangen.

Nach erreichen der Path-Consistency ist deutlich im Baum die einzig mögliche Lösung zu erkennen.

3.1.3 Stable-Sets

Eine Menge von Knoten in einem Graphen, wo einige Paare von Knoten nicht direkt miteinander verbunden sind, werden Stable-Sets genannt. Durch die Stable-Sets lassen sich Constraint-Checks einsparen und so eine Reduzierung des Suchraumes erreichen.

3.2 Meta-Strukturen

3.2.1 Biconnected-Component-Trees

Das zugrundeliegende Metaproblem besitzt immer eine Baumstruktur. Eine Metavariable besteht aus allen Variablen, die das Teilproblem besitzt. Die Metavariablen der Biconnected-Component und die Meta-Constraints sorgen dafür, daß einzelne Variablen der einzelnen Teilprobleme zusammenpassen. Ein Meta-Constraint ist ein Constraint zwischen den Metavariablen, das die Konsistenz der ursprünglichen Constraints zwischen den ursprünglichen Variablen sicherstellt. Die konstruierte Baumstruktur läßt sich mit den Algorithmen für Probleme mit Baumstruktur lösen (siehe Makro-Strukturen).

Es müssen die Mengen von Metawerten für die Metavariablen gefunden werden. Das betrifft Teilprobleme, deren Lösung mit exponentiellen Aufwand zu finden ist (hier mit b bezeichnet). Die Arc-Consistency stellt in dem Metaproblem eine (1, b - 1) Konsistenz sicher. (1, b - 1) Konsistenz bedeutet, wenn ein Wert für eine Variable gewählt wird, dann können konsistente Werte für b - 1 zusätzliche Variablen gefunden werden.

Wenn ein Metawert für eine Metavariable gewählt wird, dann ist für jeden ein konsistenter Metawert für eine andere Metavariable zu finden und man muß sich darum kümmern, daß der zweite Metawert dem ersten zugewiesen wird - so wie es mit dem Metawert in der originalen Problemvariable geschieht. Man erhält zwei gemeinsame Metavariablen. Das ist in etwa mit einer Korrektur gleichzusetzen: Der eine Wert der Variablen wird in den Metawert der zweiten Variable geändert. Zudem wird die Konsistenz mit den anderen Variablen verlangt. Durch die (1, b - 1) Konsistenz läßt sich genau das erreichen. Der Aufwand zur Erstellung der Arc-Consistency ist quadratisch.

Im Bild 6b (Erkennung von geometrischen Figuren) ist zu erkennen, daß nur der Knoten B den Graphen auftrennt. Die Entfernung von E trennt den Graphen nicht! Auf eine identische Belegung der Variablen B in den Metaproblemen P und Q ist zu achten.

3.2.2 K-Tree-Clique-Trees

Hier soll eine alternative Näherung beschrieben werden, die diese Forderung erfüllt.  Das Problem, überführt in eine Darstellung von CSPs mit Zyklen, ist mit einem Aufwand von O(n· d^(k+2)) zu lösen (siehe Bild 9). Alle Constraints von dem Ausgangsproblem sind Constraints innerhalb eines oder mehrerer Teilprobleme im Metaproblem. Das Metaconstraint erzwingt eine Lösung zu dem Metaproblem. Dabei kann eine originale Problemvariable nicht zwei unterschiedliche Werte annehmen. Es ist möglich, innerhalb der Suche nach der Lösung die maximalen Gruppen von jedem K-Baum in ein baumstrukturiertes Metaproblem umzuorganisieren (siehe Bild 9b).  Eine maximale Gruppe ist eine Menge von Variablen, die, zusammengefaßt zu einer Metavariablen, maximal zwei Nachbarn hat. Sobald ein solcher Gruppenbaum (bestehend aus maximalen Gruppen) fertig ist, kann er dem Algorithmus zur Findung der Arc-Consistency zugeführt werden. Danach können die Constraints wieder zurück auf die anfänglichen Problemvariablen zurückgeführt werden. Dabei werden alle Lösungen aus der Lösungsmenge herausgenommen, die eine Belegung einer Variablen mit zwei unterschiedlichen Werten zu Folge hätte (siehe Bild 9c). Durch die Variable-Completability wird sichergestellt, das sich die Metaprobleme (mit ihren Metavariablen und Metawerten) in dem Sinne lösen lassen, daß das Ergebnis der Metavariablen der Lösung der Variablen des Ausgangsproblems entspricht. Für das Ausgangsproblem kann nun eine Lösung dem Suchbaum entnommen werden.

Bild 9 zeigt wie über die Gruppenbildung ein Suchbaum erzeugt werden kann. Der Graph in Bild 9a kann z.B. in die Teilgraphen mit den Knoten WXY, XYZ und XVZ zerlegt werden (maximale Gruppen). In diesen Teilgraphen wird nun die Arc-Consistency hergestellt. Die Metavariablen erhalten den Namen der Knotengruppen und in ihnen werden die konsistenten Wertebelegungen eingetragen (siehe Bild 9b):
 

WXY = {(a, b, c), (b, a, c)},   XYZ = {(a, c, b), (b, a, c)},   XVZ = {(a, c, b), (b, a, c)}.

Nun ist die Konsistenz zwischen den einzelnen Metaproblemen, den Metavariablen herzustellen. Die Belegung von WXY = (a, b, c) ist zu keiner Belegung der Metavariablen XYZ konsistent. Also kann (a, b, c) aus der Wertemenge von WXY entfernt werden. Mit WXY = (b, a, c) ist die Belegung XYZ = (a, c, b) konsistent. Jetzt sind die Belegungen von XYZ und WXY zu überprüfen. XYZ = (b, a, c) ist nicht zu WXY = (b, a, c) konsistent und fällt heraus (WXY = (a, b, c) ist bereits vorher herausgefallen). Entsprechend wird mit den Metavariablen XYZ und XVZ verfahren. Dabei ist die Belegung von XVZ = (b, a, c) inkonsistent und der Graph in Bild 9c entsteht.

3.2.3 Separator-Pseudotrees

Durch eine rekursive Entfernung von Separatoren von einem Graphen kann ein Metaproblem mit einer Pseudotree-Struktur erzeugt werden. Die zugrundeliegende Struktur des Graphen wird durch einige zusätzliche Kanten zwischen einem Knoten und einem Vorgänger von diesem Knoten in dem Baum erzeugt. Bei der Erstellung des Baumes liefert der erste Separator die Wurzel. Es ist möglich, daß das Herausnehmen einer Variablen nicht zum Trennen des Graphen ausreicht. Dann müssen ausgewählte Knoten zu einer Metavariablen zusammengefaßt werden, die das gewährleisten. Weiter werden alle Teile des Constraint-Graphen, durch Bildung von Separatoren, in Teilprobleme zerlegt und dem Pseudotree angefügt. Gibt es keine Möglichkeit, den Graphen weiter zu zerteilen, dann hängt man einfach die untrennbaren Teile als Knoten an den Pseudotree an. Zusätzliche Meta-Constraint-Kanten könnten eventuell notwendig werden, um die Abhängigkeiten zwischen einzelnen Teilproblemen korrekt wiederzugeben.

Weil der Baum durch den Prozeß der Zerteilung generiert wurde, kann es keine Kanten in dem Baum geben, die einen linken Teilbaum mit einem rechten Teilbaum verbinden. Würde beispielsweise zwischen zwei Teilproblemen kein Constraint existieren, dann können diese auch nicht in Teilprobleme zerlegt werden. Wir können versuchen, die Metavariablen Stufe für Stufe im Pseudotree zu belegen. Innerhalb jeder Stufe bilden die Metavariablen ein Stable-Set. Von da an kann der Algorithmus der Stable-Sets verwendet werden. Wenn beim traversieren des Baumes auf der entsprechenden Ebene kein Metawert für eine Metavariable zu finden ist, dann garantiert die Pseudotree-Struktur, daß auf einer der übergeordneten Ebenen eine Metavariable neu belegt werden muß, die das weitere traversieren des Baumes ermöglicht. Diese Beobachtung unterstützt einen Suchalgorithmus der eine exponentielle Schranke über die Anzahl der Ebenen im Pseudotree besitzt.

In Bild 10a ist der Ausgangsgraph zu sehen. Zwei sinnvolle Möglichkeiten eine Biconnected-Component zu wählen besteht aus den Knoten XZ oder UV. Bei der Wahl von XZWUV wird die weitere Zerlegung nur aufgeschoben. Im Beispiel wurden die Knoten U und V zur Metavariable UV zusammengefaßt (siehe Bild 10b).  Jetzt kann der Separator UV aus dem Graphen mit seinen Constraints entfernt werden und dient als Wurzel im Pseudotree. Jetzt besteht der Graph aus zwei Biconnected-Component-Graphen: T und XYZW. Von daher besitzt UV genau zwei Nachfolger. Da T nicht teilbar ist, wird die Metavariable XZ als nächster Separator und T als Blatt im Pseudotree an UV gehängt. Für später ist das Constraint zwischen UV und W zu merken (*).  Y und W wurden durch den Separator XZ aufgetrennt und werden daher an diesem als Knoten am Pseudotree erscheinen. Sie sind die letzten Separatoren. Daher bilden sie die Blätter an XZ.

Nachdem UV aus dem Graphen entfernt wurde ist das Constraint zu W verloren gegangen (XZ und T sind Blätter von UV). Das Constraint zwischen UV und W wird im Pseudotree nachträglich als Metaconstraint eingetragen (siehe Bild 10c).

3.3 Mikro-Strukturen

Ohne Beispiel und Algorithmus sind hier zur Vollständigkeit die Cartesian-Product-Representation und Consistent-Subproblems angeschnitten. [FRE93].

3.3.1 Interchangeability

Glücklicherweise gibt es eine lokale Entscheidungshilfe, damit zwei Werte ausgetauscht werden können. Eine hinreichende Bedingung für die Austauschbarkeit zweier Werte einer Variable ist die Neighborhood-Interchangeability. Werte einer Variable, z. B. a und b, sind konsistent mit allen Werten anderer Variablen, d. h. a und b sind Neighborhood-Interchangeable. Bis zu diesem Zeitpunkt erhalten wir alle Lösungen ohne Inkonsistenz. Auf die gleiche Weise wie lokale Inkonsistenz (Arc-Consistency) vermieden wird, können Neighborhood-Interchangeable Werte entfernt werden. Das ist in einem quadratischen Zeitaufwand möglich. Von der Neighborhood-Interchangeability gibt es eine Anzahl von Variationen.

Beispiel: Angenommen eine Variable A hat unter anderem die Werte a und b. Der Wert a läßt sich durch b substituieren, wenn sich a in jeder Lösung durch b ersetzen läßt (siehe Bild 11). In diesem Falle kann a durch b in einem frühen Stadium der Suche ersetzt werden. Erlaubt ist die Substitution bei mehreren Werten, um die Neighborhood-Interchangeability zu entfernen. Alle Lösungen, die ohne a gefunden werden (substituiert durch b), sind durch den ersatzlosen Wegfall von a nicht leichter zu finden. Wenn eine Lösung betreffend b gefunden wurde, dann kann a nicht durch b substituiert werden. Es gibt keine Garantie für die Lösung, die b betrifft, wenn b durch a substituiert wurde. Hier sei nochmals betont, daß durch lokale Kriterien die Entscheidung über die Substitution von a durch b entschieden werden.

Bild 11a zeigt den Constraint-Graphen des Problems. Im Bild 11b ist die Mikro-Struktur dargestellt. Man kann erkennen, daß die Domäne von B mit denen von A und C vollständig konsistent sind. In B können c und d ausgetauscht (Neighborhood-Interchangeability) oder aber auch c durch d substituiert werden, ohne einen Widerspruch zu erhalten (siehe Bild 11c).

3.3.2 Cartesian-Product-Representation

3.3.3 Consistent-Subproblems

4 Zusammenfassung

Am Ende soll nicht unerwähnt bleiben, daß es in der Praxis oft sehr schwierig ist das Problem zu analysieren und eine geeignete Struktur zu finden, auf deren Grundlage ein effizienter Algorithmus implementiert werden kann.  Nach der Analyse des Problems ist individuell eine geeignete Wahl bzgl. des Lösungsalgorithmus zu wählen.

5 Quellen

Links:
[BAR98]: Guide to Constraint Programming, Roman Barták, 1998
         http://kti.ms.mff.cuni.cz/~bartak/constraints/consistent.html