Title:

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

Description:  Was sind Constraints und Constraint-Programmierung?
Author:Bernd Schröder und Stefan Pohle
deutsch
  
ISBN: 3423050012   ISBN: 3423050012   ISBN: 3423050012   ISBN: 3423050012 
 
  Wir empfehlen:       
 

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


Kurzbeschreibung

In dieser Ausarbeitung sollen verschiedene Möglichkeiten aufgezeigt werden, wie mit CSPs und Constraints umgegangen werden kann. Es werden Verfahren zur Domainreduktion von Variablen, Prüfung von Konsistenzen und verschiedene Darstellungsarten für CSPs und darauf basierende Lösungsalgorithmen vorgestellt.
 

Inhalt

1 Einleitung 1.1 Was sind Constraints?
1.2 Was ist Constraint-Programmierung?
2 Konsistenz 2.1 Node-Consistency
2.2 Arc-Consistency
2.3 K-Consistency (Path-Consistency)
3 Strukturen 3.1 Makro-Stukturen 3.1.1 Trees
3.1.2 K-Trees
3.1.3 Stable-Sets
3.2 Meta-Strukturen 3.2.1 Biconnected-Component-Trees
3.2.2 K-Tree-Clique-Trees
3.2.3 Separator-Pseudotrees
3.3 Mikro-Strukturen 3.3.1 Interchangeability
3.3.2 Cartesian-Product-Representation
3.3.3 Consistent-Subproblems
4 Zusammenfassung

5 Quellen


1 Einleitung

Die folgende Arbeit soll einen Einblick in die Struktur- und Konsistenzeigenschaften von Constraint-Satisfaction-Problems (CSPs) geben. Bei einem CSP besteht die Aufgabe darin, verschiedene Variaben mit Werten aus ihren jeweiligen Wertemengen zu belegen. Diese Wertemengen werden als Domänen
bezeichnet und können für jede Variable verschieden aussehen. Für die Belegung einer Variablen mit einem Wert aus ihrer Domäne können zusätzlich (Rand-)Bedingungen definiert sein, die die zulässigen Werte der entsprechenden Variablen einschränken. Diese Randbedingungen werden Constraints genannt.
Ziel der Constraint-Programmierung  ist es, Möglichkeiten aufzuzeigen, effizient nach Lösungen für verschiedene Variablen zu suchen.

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.<<

Bild 1. Graph-Coloring-Problem
Bild 1. Graph-Coloring-Problem

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.

Bild 2. Darstellung eines Suchbaums mit vollständiger Enumeration
Bild 2. Darstellung eines Suchbaums mit vollständiger Enumeration

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.

Bild 3. Beispiel zur Erkennung von geometrischen Figuren
Bild 3. Beispiel zur Erkennung von geometrischen Figuren

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 bilden bzw. definieren Aussagen von Beziehungen zwischen einer Menge von Variablen X={x1,...,xn}, wobei die Werte, die von Variablen angenommen werden können, im Vordergrund stehen. Die Menge Di von Werten einer Variablen xi wird Domain genannt. Das Bestreben ist es, eine eindeutige Belegung für alle Variablen zu finden, so daß keine Widersprüche bzgl. der aufgestellten Menge von Constraints entstehen, d.h., die Werte der Variablen erfüllen die Constraints. Die Darstellung des CSPs erfolgt durch einen Constraint-Graphen, in dem die Variablen auf Knoten und die Constraints auf Kanten zwischen den Knoten abgebildet werden (siehe Bild 4). In die Knoten werden die Domains der entsprechenden Variablen eingetragen, die Kanten werden mit den für dieses Constraint entsprechenden gültigen Variablenbelegungen beschriftet.
Bild 4. Constraint-Graph zum Graph-Coloring-Problem
Bild 4. Constraint-Graph zum Graph-Coloring-Problem

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?

Bei der Lösung eines Problemes wird normlerweise der gesamte Suchbaum aufgespannt, es erfolgt eine vollständige Enumeration. Meistens sind nicht alle Teilbäume von Interesse, da sie zu keiner Lösung führen. Eine Lösung läßt sich mittels vollständiger Enumeration nur ineffizient finden.

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

Erfüllen Variablen die Constraints, dann spricht man davon, daß die Variablen bzgl. der Constraints konsistent sind. Dabei wird zwischen lokaler und globaler Konsistenz unterschieden. Lokal konsistent sind beispielsweise zwei Variablen, die die verbindenden Constraints erfüllen. Es kann allerdings sein, daß die lokal konsistenten Werte einer dieser Variablen aber ein weiteres Constraint zu einer dritten Variable nicht mehr erfüllen können. Dann ist zwar lokale Konsistenz erreicht, aber eine global konsistente Lösung ist nicht mehr möglich.

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

Der einfachste Konsistenzcheck ist die Node-Consistency. Dabei werden die unären Constraints der Variable abgearbeitet und die Werte aus den entsprechenden Domains der Variablen entfernt, so daß die zugehörigen Constraints unären Constraints erfüllt werden. [BAR98].

2.2 Arc-Consistency

Wenn in dem Graphen die Node-Consistency hergestellt wurde, können alle unären Constraints gelöscht werden, da bereits sichergestellt ist, daß diese immer erfüllt werden. Die binären Constraints lassen sich jetzt mit der Arc-Consistency überprüfen. Eine Idee wie das funktioniert ist bereits in den vorherigen Abschnitten gegeben worden. Dabei werden die Constraints in der Art überprüft, daß für alle Belegungen einer Variablen eine konsistente Belegung der anderen gesucht wird. Ist dies nicht der Fall, so wird der entsprechende Wert der ersten Variablen aus deren Doman gelöscht. Sollte dabei eine der Domains leer werden, so läßt sich keine lokal konsistente Lösung finden und damit auch keine global konsistente.

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 (Vi,Vj)
  DELETE <- false;
  for each X in Di do
    if there is no such Y in Dj such that (X,Y) is consistent,
    then
      delete X from Di;
      DELETE <- true;
    endif;
  endfor;
  return DELETE;
end REVISE
 
Prozedur zum Erreichen der Arc Consistency:
procedure AC-3
  Q <- {(Vi,Vj) in arcs (G), i # j};
  while not Q empty
    select and delete any arc (Vk,Vm) from Q;
    if REVISE (Vk,Vm) then
      Q <- Q union {(Vi,Vk) such that (Vi,Vk) in arcs (G), i # k, i # m}
    endif
  endwhile
end AC-3
Bild 5. Beispiel zur für den Algorithmus zur Erreichung der Arc-Consistency
Bild 5. Beispiel zur für den Algorithmus zur Erreichung der Arc-Consistency

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 (Vi, Vj) von der Kante (Vj, Vi) 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) }
Die Kanten werden in einer beliebig gewählten Reihenfolge abgearbeitet. Im Beispiel werden die Kanten in der Reihenfolge, wie sie in Q abgelegt sind, bearbeitet. Bei den ersten drei Kanten gibt es noch keine Probleme, um für eine Belegung von B einen entsprechenden konsistenten Wert einer Nachbarvariaben zu finden. Für die Kante (C, B) mit dem Wert b für C kann allerdings keine Konsistenz erreicht werden. b wird aus der Domain von C gelöscht und die Kanten (D, C) und (E, C) werden in die Menge Q eingefügt (sofern noch nicht vorhanden). Durch den gelöschten Wert können bei den benachbarten Variablen inkonsistenzen entstehen. Zwei Variablen, verbunden durch ein Constraint, werden als benachbart bezeichnet.  Als nächstes fällt der Wert e für die Variable C ebenfalls weg (wg. (C, E)) und Q wird um die Kanten (B, C) und (D, C) erweitert. Am Ende bleiben für die Variablen A, B, C, D und E nur noch die Domains {a}, {b}, {c}, {d} und {e} übrig. [BAR98].

2.3 K-Consistency

Es ist im allgemeinen nicht möglich, nach Erreichen der Arc-Consistency eine Backtrack-Free-Search durchzuführen. Die Arc-Consistency kann erweitert werden, indem der durchsuchte Pfad verlängert wird. Bei der Node-Consistency handelt es sich um eine 1-Consistency und bei der Arc-Consistency um eine 2-Consistency. K gibt die Anzahl der Variablen an, für die lokale Konsistenz erreicht wird. Im allgemeinen wird die K-Consistency auf eine 3-Consistency beschränkt. Längere Pfade werden aus Effizienzgründen in der Praxis eher selten verwendet. Die 3-Consistency wird Path-Consistency genannt.

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

Viele CSPs lassen sich im Prinzip einer Struktur zuordnen. Sie können also eine bestimmte Struktur besitzen. Für CSPs, die eine Baumstruktur besitzen, existieren effiziente Algorithmen. Allerdings ist diese Art von CSPs nur sehr selten anzutreffen. Von daher liegt es nahe CSPs mit beliebiger Struktur in ein Pseudo-CSP mit Baumstruktur umzuwandeln.

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.

Bild 6. Beispiele für drei Arten von Strukturen
Bild 6. Beispiele für drei Arten von Strukturen

3.1 Makro-Strukturen

Makro-Strukturen behandeln die Lösung der CSPs mit Baumstruktur. Mit diesen Methoden soll ein Baum so umgeordnet werden, daß in einem Zuge eine Lösung des CSPs, von der Wurzel auf beliebigen Wege zu den Blättern des Baumes gefunden wird. In dem Baum kann eine Suche ohne Backtracking garantiert werden. [FRE93].

3.1.1 Zyklenfreie CSP-Graphen

Besitzt der Constraint-Graph eines zu lösenden CSPs eine Baumstruktur, dann ist der Constraint-Graph zyklenfrei. Der Constraint-Graph kann durch eine spezielle Anordnung der Knoten in ein Directed-Constraint-Graph umgewandelt werden (siehe Bild 7). Die Variable mit den meisten Kanten bildet die Wurzel des neuen Baumes. Die Variablen werden so umgeordnet, daß sie nicht von mehr als einer vorangehenden Variable abhängig sind. Jeder Knoten hat nicht mehr als einen Vorgänger. Ein Vorgänger ist der Knoten direkt eine Ebene höher im Baum, ausgenommen der Wurzel. Die Variable und deren Constraints, die als Knoten im neuen Baum benutzt wird, ist für die Berechnung der eingehenden Kanten der weiteren Knoten nicht mehr zu beachten.

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.
Alle drei Schritte können in einer linearen (anstelle exponentieller) Zeit, in Abhängigkeit von der Anzahl der Variablen, ausgeführt werden.

Bild 7. Umwandlung eines zyklenfreien Graphen in ein Arc-Consistent-Ordered-Graphen
Bild 7. Umwandlung eines zyklenfreien Graphen in
ein Arc-Consistent-Ordered-Graphen

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

Baumstrukturen können als K-Bäume verallgemeinert werden, wobei Bäume der Breite 1 1-Bäume sind. Ein Directed-Constraint-Graph mit der Breite k ist ein Graph, in welchem k das Maximum der Anzahl von Kanten von einer Variable zu den vorhergehenden Variablen ist (siehe Bild 8). D. h., die Breite eines Knotens ist die Anzahl der Kanten zu den Nachbarknoten. Die Breite eines Graphen ist das Maximum aller Breiten seiner Knoten.

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.
Das Ergebnis ist ein Algorithmus zur Lösung eines K-Baums mit linearen Aufwand in Abhängigkeit von der Anzahl der Variablen (die maximale Schranke beträgt (d(K+1)), d ist eine Funktion von dem Maximum der Bereichsgrenze).

Bild 8. Umwandlung eines Constraint-Graphen in einen k + 1 Consist-Ordered-Constraint-Graphen
Bild 8. Umwandlung eines Constraint-Graphen in einen k + 1 Consist-Ordered-Constraint-Graphen.

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

Ohne Algorithmus seien hier noch zur Vollständigkeit die Stable-Sets erwähnt. Hat eine Menge von Variablen in einem Problem keine gemeinsamen Constraints so kann das unter Umständen die Suche nach einer Lösung im Suchbaum verkürzen.

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

Die Struktur eines komplexen CSPs wird geschickt in Teilprobleme zerlegt, dessen Graph anders angeordnet, einen neuen Graphen mit einer Baumstruktur ergibt (siehe CSPs mit zyklenfreien Graphen - Erstellung eines Direct-Ordered-Graphen). Das so entstandene Metaproblem (bestehend aus den Teilproblemen) wird in einem Meta-Constraint-Graphen dargestellt. Dieser läßt sich dann mit den im Kapitel 3.1 (Makro-Strukturen) beschriebenen Algorithmen effizient lösen. Kleine Probleme (Teilprobleme) lassen sich im allgemeinen leichter lösen. [FRE93].

3.2.1 Biconnected-Component-Trees

Ein Graph ist Biconnected, wenn das Entfernen eines Kontens den Graphen nicht in zwei Teilgraphen zerlegt (siehe Bild 6b). Der maximale Biconnected-Teilgraph von einem Graphen wird als dessen Biconnected-Component bezeichnet. Die größte Biconnected-Component jedes CSPs ist in exponentieller Zeit berechenbar (siehe [FRE93]). Alle anderen Biconnected-Components sind in O(n²) auffindbar.

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

Oft interessiert man sich nur für Werte einer Variablen, die auch Teil der global konsistenten Lösung sind. Dies wird Variable-Completability genannt. Es besteht natürlich die Möglichkeit, alle Lösungen zu suchen und die Werte einer Variablen zu löschen, die nicht Bestandteil einer Lösung sind. Das Problem, alle Werte einer Variablen zu entfernen, die nicht zur Lösung beitragen kann allerdings vereinfacht werden.

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. Gruppenbildung zur Erzeugung eines Suchbaumes ohne Backtracking
Bild 9. Gruppenbildung zur Erzeugung eines Suchbaumes ohne Backtracking

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

Im folgenden Abschnitt wird die Trennung von Graphen in Biconnected-Component-Trees diskutiert. Es gibt mehrere Wege einen Graphen in Teilstücke durch die Entfernung von Knoten aufzutrennen (siehe Bild 10). Die fehlenden Knoten werden Separator genannt.

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.

Bild 10. Umwandlung eines Biconnected-Graphen in eine Baumstruktur
Bild 10. Umwandlung eines Biconnected-Graphen in eine Baumstruktur

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

Mit Hilfe der Mikro-Strukturen versucht man die Wertemengen der Variablen und damit die Constraint-Checks zu reduzieren. Dadurch entstehen Teillösungen oder aber eine Reduktion des Suchbaumes. Dann kann das Problem, wenn nötig, mit Hilfe der Meta-Strukturen in eine Baumstruktur umgewandelt und mit Hilfe der Makro-Strukturen gelöst werden.

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

3.3.1 Interchangeability

Sind die Werte von Variablen in dem Sinne auswechselbar, daß sie in derselben Lösung erscheinen, so nennt man das Interchangeability. Besitzt die Lösung einer Variablen einen Wert und es gilt für diese Variable die Interchangeability, dann kann durch Substitution ein anderer Wert eingesetzt werden. Es entsteht eine neue Lösung. Damit der Suchraum durch Entfernen von Werten vor der Suche einer Lösung vereinfacht werden kann, muß man garantieren, daß durch den Wegfall der Werte noch alle Lösungen möglich sind. Um die Suche nach einer Lösung zu vereinfachen wird ein Wert einer Variable gelöscht, von dem angenommen wird, daß durch den fehlenden Wert keine Lösungen verlorengehen.

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 11. Substitution zur Löschung der Neighborhood-Interchangeability
Bild 11. Substitution zur Löschung der Neighborhood-Interchangeability

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

Bei dieser Repräsentation werden alle Kombinationen von konsistenten Belegungen zweier Variablen als Kreuzprodukt dargestellt. Das bedeutet, daß die Menge von Werten einer Variablen immer konsistent zu allen anderen Werten der zweiten Variablen sind. Als Beispiel dient wieder das Graph-Coloring-Problem. Dabei kann man sich drei Variablen A, B und C mit den Belegungen
 
  A = {a, b, c}, B = {d, e, f} und C = {g, h}
vorstellen. Alle konsistenten Paare von A und B sind
 
  {a, b, c} X {d, e, f}.
Bei Hinzunahme von C können nun alle Werte von C mit denen von A und B auf Konsistenz überprüft werden. Es gibt eine effizientere Möglichkeit: ohne jedes von den neun Paaren individuell zu überprüfen, werden nur noch die Werte aus den entsprechenden Variablenmengen zur Prüfung herangezogen. Z. B.  sind mit A X B = {(a, d), (a, e), (a, f), (b, d), (b, e), (b, f), (c, d), (c, e), (c, f)} insgesamt 18 Konsistenz-Checks mit C sind notwendig. Durch die Cartesian-Product-Representation sind dann nur noch insgesamt 12 Constraint-Checks notwendig. Die Werte von A und B werden mit denen von C verglichen, also (3 + 3) * 2. Durch die Andeutung des Verfahrens soll deutlich werden, daß die Anzahl der Constraint-Checks verringert oder zumindest nicht erhöht wird, um alle Lösungen eines Problems zu finden.

3.3.3 Consistent-Subproblems

Das Aufstellen des Consistency-Graphen würde zeigen, daß der Wert a für die Variable W konsistent zu den Werten b und c für die Variablen X und Z ist und zu allen Werten der Variablen Y. Dieses Teilproblem wird im Constraint-Graphen dargestellt, in dem die Werte der Variablen X, Y und Z hinsichtlich der Konsistenz zum Wert a der Variablen W eingeschränkt wurden und der Wertebereich der von W weiterhin alle Werte außer a enthält. Dies wird als Consistent-Subproblem bezeichnet, was den Wert a der Variablen W betrifft. Wenn nur eine Lösung von Interesse und eine Lösung möglich ist, dann kann dieses Teilproblem vernachlässigt werden [FRE93]. Dadurch wird die Anzahl der Constraint-Checks stark reduziert.

4 Zusammenfassung

In dieser Ausarbeitung wurde gezeigt, wie die Einhaltung von Constraints zwischen Variablen sichergestellt wird und daß sich CSPs in Graphen darstellen lassen, die sich in eine Baumstruktur umwandeln lassen. Für Baumstrukturen gibt es die Möglichkeit, Suchbäume zu generieren, in denen ohne Backtracking nach Lösungen gesucht werden kann.

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

[FRE93]: E. C. Freuder: "Exploiting Structure in Constraint Satisfaction Problems",
         Section 2.1 in Constraint Programming, NATO ASI Series, 1993.
[SHA93]: S. C. Shapiro (ed.): "Encyclopedia of AI", 2nd edition, vol. 1,
         section on constraint networks, Wiley, 1993.
[FRE82]: E. C. Freuder: "A Sufficient Condition for Backtrack-Free Search", JACM,
         vol. 29, no. 1, January 1982, pp. 24-32.
[DEC92]: R. Dechter: "From Local to Global Consistency",
         Artificial Intelligence 55 (1992), pp. 87-107.

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

  
Bürgerliches Gesetzbuch BGB: mit Allgemeinem Gleichbehandlungsgesetz, BeurkundungsG, BGB-Informationspflichten-Verordnung, Einführungsgesetz, ... Rechtsstand: 1. August 2012
Siehe auch:
Handelsgesetzbuch HGB: ohne Seehandelsrecht, mit …
Strafgesetzbuch StGB: mit Einführungsgesetz, …
Grundgesetz GG: Menschenrechtskonvention, …
Arbeitsgesetze
Basistexte Öffentliches Recht: Rechtsstand: 1. …
Aktiengesetz · GmbH-Gesetz: mit …
 
   
 
     

This web site is a part of the project StudyPaper.com.
We are grateful to Bernd Schröder und Stefan Pohle for contributing this article.

Back to the topic site:
StudyPaper.com/Startseite/Computer/Informatik

External Links to this site are permitted without prior consent.
   
  deutsch  |  Set bookmark  |  Send a friend a link  |  Copyright ©  |  Impressum