Kapitel 2

Seminarvorträge

2.1 Constraint Programming (Tobias Spribille)

2.1.1 Einführung

Ein Computer ist von seiner Grundstruktur her für eine imperative Vorgehensweise bei der Problemlösung geschaöen. Dies schlägt sich auch in den meisten gängigen Programmiersprachen und bekannten Algorithmen nieder: Um ein Problem zu lösen, wird eine Folge von konkreten Handlungsanweisungen angegeben, die aus einem Startwert die zugehörige Lösung berechnen. Alle Eigenschaften der Lösung sind implizit in den einzelnen Teilen der Rechenvorschrift enthalten. Deshalb ist einem Programm oft nicht leicht anzusehen, was es überhaupt macht. Ebenso aufwendig kann es sein, zu einem Problem einen Algorithmus zu ?nden, der die Lösung berechnet, deren Eigenschaften oft recht einfach anzugeben sind.

Von eben diesen Eigenschaften der Lösung geht das deklarative Programmierparadigma aus, das in Sprachen wie z.B. PROLOG zum Einsatz kommt. Der Programmierer beschreibt in einer formalen Syntax die Eigenschaften, die die gesuchte Lösung haben soll, und das System ermittelt diese daraus.

int fib(int x)
{
int f1 = 0, f2 = 1;
while (x-- >= 1)
{
int temp = f1 + f2;
f1 = f2;
f2 = temp;
}
return f2;
}

fib(0,0).
fib(1,1).
fib(N,X) :- fib(N-1,Y),
fib(N-2,Z),
X is Y+Z.

Abbildung 2.1: Imperative und deklarative Berechnung der Fibonacci-Zahlen

11

Seite 11: vorherige Seite | nächste Seite | Übersicht

12 KAPITEL 2. SEMINARVORTRÄGE

Die Bezeichnung Constraint Programming steht für solche deklarativen Problemlösungsmethoden, bei denen für eine Menge von Variablen Werte gefunden werden müssen, die einer Menge von Bedingungen (den constraints) genügen.

Zu deklarativ spezi?zierten Problemen gibt es im Unterschied zu den imperativen Verfahren nicht immer eine eindeutige Lösung. Für praktische Problemstellungen wie die Transportoptimierung ist es aber ausreichend, irgendeine mögliche Lösung zu ?nden, die alle Anforderungen erfüllt.

Ein PROLOG-Interpreter ?ndet die Lösung mit den angegebenen Eigenschaften durch eine Tiefensuche im exponentiell groflen Lösungsraum. Dies kann bei groflen Problemen sehr lange dauern. Deshalb werden für Constraint Programming spezielle Lösungsalgorithmen benutzt, die durch geschickte Wahl der Suchrichtung und/oder Einsatz von Heuristiken möglichst früh auf eine Lösung stoflen sollen oder die Anzahl der zu betrachtenden Möglichkeiten reduzieren.

2.1.2 Grundlagen

De?nition 2.1.1 Ein Constraint Satisfaction Problem (oder kurz CSP) ist ein Tripel (V ; W ; C), bestehend aus:

- Einer Menge von Variablen V = fV1; : : : ; Vng mit Wertebereich W .

- Einer Menge von Constraints C = fC1; : : : ; Crg. Ein Constraint ist eine Beziehung zwischen Variablenwerten:

Cj : P(V) ? (V !W) ! B
fö(Vi1); : : : ; ö(Vik )g 7! ftrue, falseg

Gesucht ist eine Variablenbelegung ö 2 (V !W), die alle Constraints erfüllt:

8j 2 f1; : : : ; rg : Cj(fVi1 ; : : : ; Vik g; ö) = true

De?nition 2.1.2 Ein hierarchisches CSP de?niert zusätzlich eine Hierarchie auf den Constraints:
H : C ! f1; : : : ; hmaxg

Constraints, die höher in der Hierarchie stehen, sind wichtiger als tiefere, und ihre Erfüllung hat Priorität vor allen anderen Constraints.

Es gibt verschiedene Arten von CSPs:

- ein unterbestimmtes (underconstrained) CSP hat mehrere Lösungen, da die Constraints nicht alle Variablen eindeutig bestimmen. Da in vielen Anwendungen nicht der Benutzer entscheiden kann, welche Lösung gewählt werden soll, könnte hier mit Heuristiken versucht werden, dessen Intention zu treöen.

- ein überbestimmtes (overconstrained) CSP enthält mehr Constraints, als zur eindeutigen Bestimmung der Variablenwerte notwendig wären. Dies ist auf zwei verschiedene Arten möglich:

>= Einige Constraints sind redundant, d.h. es kann eine Lösung gefunden werden, die allen Constraints genügt (aber bereits mit einer Teilmenge auch gefunden worden wäre)

Seite 12: vorherige Seite | nächste Seite | Übersicht

2.1. CONSTRAINT PROGRAMMING 13

>= Es entsteht ein KonÄikt, da nicht alle Constraints gleichzeitig erfüllt werden können. Über eine Hierarchie kann von vornherein festgelegt werden, welche Constraints in einem solchen Fall wichtiger sind, und welche am ehesten wegfallen dürfen. Eine Möglichkeit der KonÄiktlösung ist auch, die Lösung mit dem minimalen Fehler zu wählen.

- Probleme mit dynamisch sich ändernden Constraints lassen sich mit inkrementellen Verfahren lösen, die die Constraints in ihrer Entstehungsreihenfolge einzuplanen versuchen. Bei einer Änderung mufl meist nur ein kleiner Teil der Werte neu berechnet werden, so dafl sich diese Verfahren besonders für interaktive Anwendungen eignen.

2.1.2.1 Vorteile von Constraint Programming

Aus den bisher vorgestellten Eigenschaften lassen sich bereits einige Vorteile von Constraint Programming gegenüber expliziten Lösungsverfahren für ein Problem erkennen:

- Man mufl nur die Eigenschaften einer Lösung beschreiben, nicht den Weg dorthin

- Bedingungen können sich dynamisch ändern (in Form von zusätzlichen Constraints)

- lokale Zusammenhänge können ein globales Verhalten beschreiben

2.1.3 Anwendungsbeispiele

2.1.3.1 Robotersteuerung

Einfache Roboter wie den Kran in Bild 2.2 links lassen sich noch recht einfach durch explizite Angabe der Bewegung für die einzelnen Teile steuern. Mit zunehmender Anzahl der Freiheitsgrade werden die Zusammenhänge jedoch so komplex, dafl dies nicht mehr ohne weiteres möglich ist. Für die Roboterhand in Bild 2.2 rechts müssen zahlreiche mechanische Beziehungen zwischen den sieben Teilen berücksichtigt werden. Diese können als Constraints formuliert werden, aus denen dann ein geeigneter Lösungsalgorithmus die Bewegung der einzelnen Teile ermittelt.

Abbildung 2.2: Roboter mit wenigen und vielen Freiheitsgraden

Hier ist gut erkennbar, wie sich lokale Constraints (Bedingungen an den Gelenken, die nur die Lage zweier benachbarter Glieder beschreiben) auf das globale Verhalten des Roboters auswirken.

Seite 13: vorherige Seite | nächste Seite | Übersicht

14 KAPITEL 2. SEMINARVORTRÄGE

2.1.3.2 Selbsterklärende Simulation

Ein Simulationssystem, dessen Wertebeziehungen durch Constraints realisiert sind, kann nicht nur gültige Werte berechnen, sondern ist überdies in der Lage, die Zusammenhänge zwischen diesen Werten zu erklären. So kann dem Benutzer auf Anfrage mit beliebigem Detaillierungsgrad mitgeteilt werden, warum eine Variable einen gewissen Wert hat. Im folgenden Beispiel könnte erklärt werden, warum die Fahrt erst um 7.30 Uhr beginnen kann.

Beispiel aus der Transportoptimierung Betrachtet werden soll ein Teilzusammenhang aus der Behindertenbeförderung: Zwei Behinderte sollen morgens von einem Fahrzeug nacheinander zu Hause abgeholt werden. Die dabei zu beachtenden zeitlichen Zusammenhänge könnten folgendermaflen als hierarchisches CSP mit drei Variablen und vier Constraints formuliert werden:

V1 : Weckzeit für den Behinderten, der zuerst abgeholt wird

V2 : Abholzeit für den ersten Behinderten

V3 : Abholzeit für den zweiten Behinderten

C1 : V1 >= 6; 5 (die Eltern des Behinderten, die ihn betreuen, wollen nicht so früh aufstehen), Stärke 1

C2 : V2 ? V1 >= 1 (bis der Behinderte fertig zum Abholen ist, dauert es eine Stunde), Stärke 3

C3 : V3 ? V2 >= 1
2 (die Fahrt von der Wohnung des ersten Behinderten zum zweiten dauert eine halbe Stunde), Stärke 4

C4 : V3 <= 7; 5 (die Eltern des zweiten Behinderten wollen früh zur Arbeit, damit sie früh Feierabend haben), Stärke 1

2.1.3.3 Intelligente Computergraphik

In der Computergraphik müssen oft geometrische Zusammenhänge zwischen Objekten erfüllt werden. Viele Graphikprogramme bieten deshalb Funktionen an, die z.B. das Zeichnen von parallelen Linien erlauben. Dadurch ist der Zusammenhang aber nur unmittelbar nach dem Einfügen der Linien gegeben. Wird eine Linie gedreht, ändern sich auch die geometrischen Zusammenhänge.

Constraints zur Überwachung solcher Beziehungen würden die zweite Linie mitdrehen und so die Parallelität aufrechterhalten. Dadurch können lokale interaktive Änderungen einen globalen Eöekt haben. Ein Objekt hat kein festes Verhalten mehr, dieses ergibt sich erst aus der Kombination von Objekt und Constraints. Durch die Angabe von Constraints ?programmiert? der Benutzer sozusagen das System [Gle95].

2.1.4 Constraints als Vorgaben

2.1.4.1 Einführung

In Abschnitt 2.1.2 wurde ein Constraint als eine Beziehung zwischen Variablen de?niert. Ein Programm, das zu einer Constraintmenge eine Variablenbelegung ?ndet, also ein CSP löst, heiflt Constraint Solver. Ein Beispiel für einen solchen Lösealgorithmus soll im folgenden betrachtet werden.

Seite 14: vorherige Seite | nächste Seite | Übersicht

2.1. CONSTRAINT PROGRAMMING 15

2.1.4.2 Disjunktive Zerlegung

De?nition In [FH95] wird ein grundlegendes Verfahren zur Lösung von Constraint Satisfaction Problems angewandt, das nach dem Verfahren Teile und Herrsche arbeitet. Die Hauptrolle spielt dabei die Zerlegung des Problems in Teilprobleme, die jedes für sich auf Lösungen untersucht werden. Damit ist diese Methode für Parallelisierung sehr gut geeignet.
Das Verfahren geht folgendermaflen vor:

Lege das Ausgangsproblem auf den Stack
while Stack 6= ;
Nimm ein Problem P vom Stack
if alle Variablen in P sind instantiiert
return(P )
else
Zerlege P in Teilprobleme fPig
Lege alle nichtleeren Pi auf den Stack
endif
endwhile
return(;)

Zunächst sind alle Variablen uninstantiiert. Sie werden instantiiert, indem bei der Zerlegung Werte oder Teile der (endlichen) Wertemengen dafür festgelegt werden. Ein Teilproblem heiflt leer, wenn der Wertebereich einer instantiierten Variablen leer ist, wenn es also keine möglichen Werte mehr gab, die mit den anderen instantiierten Variablen konsistent sind. Dabei heiflen zwei Werte für zwei Variablen konsistent, wenn es keinen Constraint gibt, der diese Wertekombination verbietet.

De?nition 2.1.3 Eine disjunktive Zerlegung ist eine Zerlegung eines Problems in Teilprobleme mit folgenden Eigenschaften:

1. Konsistenz: Die Werte instantiierter Variablen sind zueinander konsistent.

2. Reduktion: Jedes der Pi hat weniger mögliche Wertekombinationen oder mehr instantiierte Werte als P .

3. Semi-Vollständigkeit: Wenn es zu P eine Lösung gibt, dann auch zu mindestens einem der Pi.

Satz 2.1.1 Eine disjunktive Zerlegung garantiert, dafl das oben vorgestellte Zerlegungsverfahren für lösbare Probleme eine der Lösungen und sonst die leere Menge zurückgibt.

Beweis 2.1.1 Da die Wertebereiche der Variablen endlich sind, folgt aus der Reduktionseigenschaft, dafl irgendwann alle Teilprobleme entweder leer sind oder nur instantiierte Variablen besitzen.

Nun betrachtet man den Baum, der entsteht, wenn die Teilprobleme nach der Zerlegung als Knoten unter das Problem gehängt werden, von dem sie ausgehen. Dann folgt aus der Semi-Vollständigkeit, dafl auf jeder Ebene ein Knoten existiert, der eine Lösung des Wurzelproblems enthält. Wenn man diesen Pfad von der Wurzel aus verfolgt, kommt man nach endlich vielen Schritten an ein

Seite 15: vorherige Seite | nächste Seite | Übersicht

16 KAPITEL 2. SEMINARVORTRÄGE

Blatt, das alle Variablen instantiiert hat und somit eine Lösung für das Ausgangsproblem darstellt.

Weitere wünschenswerte Eigenschaften könnten sein:

1. Vollständigkeit: Jede Lösung von P ist auch Lösung mindestens eines der Pi.

2. Redundanzfreiheit: Jede mögliche Wertekombination für P existiert in höchstens einem der Pi.

3. Reduzierbarkeit: Die Summe der Gröflen (möglichen Wertekombinationen) der Pi kann kleiner sein als die Gröfle von P .

Diese Eigenschaften gelten unabhängig von der Reihenfolge, in der die Probleme und Teilprobleme betrachtet werden. Zum einen kann die Reihenfolge variiert werden, in der die Teilprobleme auf den Stack gelegt werden, zum anderen mufl die Menge der noch zu bearbeitenden Probleme gar nicht unbedingt als Stack organisiert sein. Diese Entscheidung, in welcher Reihenfolge die Teilprobleme erledigt werden, ist ein guter Ansatzpunkt für heuristische Verfahren.

Beispiel aus der Transportoptimierung Um verschiedene Arten solcher Zerlegungsstrategien vergleichen zu können, soll das Verfahren auf folgendes Beispiel angewandt werden:

Ein Fahrdienst besteht aus vier Touren pro Tag, zu denen drei verschiedene Fahrzeuge eingesetzt werden können. Da jeder Bus nach der Tour gereinigt oder für die nächste Fahrt ausgerüstet werden mufl (z.B. mit speziellen Sitzen), können zwei aufeinanderfolgende Fahrten nicht mit dem selben Fahrzeug gemacht werden (?aufeinanderfolgend? ist hier zyklisch gemeint, z.B. wenn die Autos rund um die Uhr im Schichtbetrieb eingesetzt werden).

Das Problem, die Fahrzeuge den Touren zuzuordnen, besteht also aus den Variablen T1; : : : ; T4 für die Touren, mit jeweils der Wertemenge fa; b; cg, entsprechend den drei Fahrzeugen. Die Bedingungen ergeben vier Constraints: Ci : Ti 6= Ti?1; i = 1; : : : ; 4

Backtracking Diese einfachste Form der Suche im Zerlegungsbaum de?niert die Zerlegung in zwei Teilprobleme:

- P1: Sei V1 die erste nicht instantiierte Variable, v1 2 dom(V1). Wenn v1 konsistent mit den bisher instantiierten Variablen ist, instantiiere V1 mit dom(V1) = fv1g, sonst mit dom(V1) = ;.

- P2: dom(V1) = dom(V1) n fv1g.

Ein Ausschnitt des Baumes ist in Abbildung 2.3 zu sehen. Jeder Knoten steht für ein Teilproblem, die vier Zeilen jedes Knotens geben die Wertemengen der Variablen T1 : : : T4 an. Die Werte instantiierter Variablen sind unterstrichen.

Forward Checking Da mit der Instantiierung einer Variablen sich bereits die Wertebereiche anderer Variablen verkleinern (weil Constraints manche Kombinationen von Werten mit den instantiierten Werten ausschlieflen), ist es sinnvoll, den Baum zu verkleinern, indem nur die jeweils konsistenten Werte weiterbetrachtet werden. Dies führt zu folgender Zerlegung:

Seite 16: vorherige Seite | nächste Seite | Übersicht

2.1. CONSTRAINT PROGRAMMING 17

Abbildung 2.3: Backtracking

- P1: dom(V1) = fv1g.
Für alle anderen uninstantiierten Variablen W :
dom(W ) = fw 2 dom(W ) j w ist konsistent zu v1g

- P2: dom(V1) = dom(V1) n fv1g.

Ein Ausschnitt des Baumes ist in Abbildung 2.4 zu sehen.

Backtracking mit kartesischem Produkt Hier können Variablen mit ganzen Wertemengen instantiiert werden. Jedes Element aus dem kartesischen Produkt dieser Wertemengen ist eine Lösung des Problems. Damit müssen sehr viel weniger Einzelfälle unterschieden werden (z.B. in Abbildung 2.4 die Zerlegung der Wertemenge fbcg für T4).

Sei fSig die Partition von dom(V1) in disjunkte Mengen Si. Dabei sind zwei Werte in der gleichen Teilmenge, wenn sie mit denselben Werten der bereits instantiierten Variablen konsistent sind.
Zu jeder Teilmenge Si ergibt sich das Teilproblem Pi:

- Pi: dom(V1) = Si
Für alle bereits instantiierten Variablen W :
dom(W ) = fw 2 dom(W ) j w ist konsistent zu den Werten in Sig

Ein Ausschnitt des Baumes ist in Abbildung 2.5 zu sehen.

Seite 17: vorherige Seite | nächste Seite | Übersicht

18 KAPITEL 2. SEMINARVORTRÄGE

Abbildung 2.4: Forward Checking
Abbildung 2.5: Backtracking mit kartesischem Produkt

Komplexität

Satz 2.1.2 Der Stack für die Disjunktive Zerlegung wird O(t ? jV j) Knoten grofl. Dabei ist t <= jW j die Anzahl der Teilprobleme, die bei einem Zerlegungsschritt maximal enstehen.

Beweis 2.1.2 Auf jeder Ebene des Zerlegungsbaumes können t ? 1 noch unbehandelte Knoten stehen. Da bei jedem Zerlegungsschritt eine Variable instantiiert wird, können nur jV j solche Ebenen entstehen.

Satz 2.1.3 Die Gröfle des Zerlegungsbaumes ist in O(jW jjVj).

Beweis 2.1.3 Betrachte exemplarisch Backtracking mit kartesischem Produkt: Im schlechtesten Fall gibt es genausoviele Teilprobleme wie Variablenwerte. Auf jeder Ebene wird eine Variable instantiiert, es kann also jV j Ebenen geben, deren Knoten je jW j Unterknoten haben.

2.1.5 Constraints als Beziehungen

2.1.5.1 Einführung

Mit einem deklarativen Programm kann man einfach nur Beziehungen überprüfen (z.B. wird das PROLOG-Programm von Seite 11 auf die Eingabe ?fib(7,13).? mit ?Yes? antworten, da 13 die siebte Fibonacci-Zahl ist).

Der hauptsächliche Sinn und Zweck der deklarativen Programmierung besteht jedoch darin, dafl der Rechner die Lösung selbst bestimmt, also auf Eingabe von ?fib(7,X).? mit ?X=13? antwortet.

Ebenso sind Constraints nicht nur Bedingungen, die eine potentielle Lösung auf ihre Korrektheit prüfen, sondern können auch selbständig aus gegebenen

Seite 18: vorherige Seite | nächste Seite | Übersicht

2.1. CONSTRAINT PROGRAMMING 19

Daten Werte entsprechend ihrer Bedingung berechnen: Ein Constraint, der eine Summenbeziehung ausdrückt, könnte wie in Abbildung 2.6 links dargestellt werden. Die Beziehung a+ b = c kann auf drei Arten sichergestellt werden: Sind a und b gegeben, kann man c := a + b berechnen. Genausogut liefle sich aber a := c ? b oder b := c ? a berechnen, d.h. aus zwei gegebenen Variablen kann automatisch die dritte berechnet werden, so dafl der Constraint erfüllt ist. Ein Constraint hat also keine fest de?nierten Ein- und Ausgabevariablen, sondern eine Reihe von Methoden, die angeben, wie aus einem Teil der Variablen ein anderer berechnet werden kann.

Constraints mit Methoden können zu Constraint-Netzen zusammengesetzt werden. In Abbildung 2.6 rechts ist ein Netz aus zwei Constraints abgebildet, das einen Zusammenhang aus der Transportoptimierung veranschaulicht: Aus dem Anfahrtszeitpunkt beim DRK ergibt sich durch Addieren der Fahrtzeit (Konstante dt1) die Ankunftszeit beim Behinderten. Mit einer weiteren Fahrtzeit (dt2) erhält man die Ankunftszeit an der Schule. Wie oben erläutert kann hier sowohl aus dem Abfahrtszeitpunkt beim DRK die Ankunftszeit an der Schule berechnet werden als auch umgekehrt.

Abbildung 2.6: Constraint als Wertebeziehung

2.1.5.2 Constraint-Netze am Beispiel des Solvers ?SkyBlue?

In [San95] wird der an der University of Washington entwickelte inkrementell Constraint Solver ?SkyBlue? vorgestellt, der mit Netzen aus hierarchischen Constraints arbeitet. Obwohl das allgemeine CSP NP-hart ist (siehe Abschnitt 2.1.7), gehen die Entwickler des Algorithmus' davon aus, dafl in praktisch vorkommenden Problemstellungen das Einfügen/Entfernen eines Constraints in linearer Zeit möglich ist.

Grundlegende Vorgehensweise Um eine Menge von Constraints zu erfüllen, wird zu jedem Constraint eine Methode gewählt. Aus den Variablen und den Constraints als Knoten sowie den gewählten Methoden als Kanten entsteht der Methodengraph. Kantenrichtungen geben an, welcher Constraint welche Variable setzen darf. Haben mehrere Constraints dieselbe Variable in ihrem Ausgabebereich, entsteht ein KonÄikt.

Enthält der Graph keine Zyklen und keine KonÄikte, kann eine den Constraints entsprechende Variablenbelegung ermittelt werden, indem die gewählten Methoden in topologischer Reihenfolge ausgeführt werden. Zyklen werden hier zu speziellen Knoten zusammengefaflt, die zunächst wie normale Knoten behandelt werden, und wenn die zugehörige Methode aufgerufen wird, von einem speziellen AuÄöse-Algorithmus behandelt werden.
?SkyBlue? benutzt Constraint-Hierarchien, um optimale Methodengraphen zu erzeugen. Ein Methodengraph heiflt hier optimal, wenn kein unerfüllter Cons-

Seite 19: vorherige Seite | nächste Seite | Übersicht

20 KAPITEL 2. SEMINARVORTRÄGE

traint erfüllt werden könnte, ohne dafl durch die veränderte Methodenwahl ein KonÄikt mit Constraints gleicher oder höherer Stärke auftritt.

Der SkyBlue-Algorithmus Ausgehend von leerem Methodengraph werden einzelne Constraints hinzugefügt/entfernt. In jedem Schritt wird der neu entstandene Graph optimiert und die gewählten Constraint-Methoden werden ausgeführt, damit die Variablenwerte die jeweiligen Constraints erfüllen.

Wird ein neuer Constraint hinzugefügt bzw. ein bestehender entfernt, versucht der Algorithmus, die nicht erfüllten Constraints durch die Konstruktion von Methoden-Ketten zu erfüllen. Können in einem Methodengraphen keine zusätzlichen Constraints durch Methoden-Ketten erfüllt werden, ist dieser optimal.

Methoden-Ketten Um einen Constraint zu erfüllen (den Ausgangsconstraint der Kette), wählt ?SkyBlue? eine Methode dieses Constraints. Steht diese Methode in KonÄikt mit anderen, bereits erfüllten Constraints, werden diese zunächst aufgehoben. Gleichstarke oder stärkere Constraints müssen wieder erfüllt werden, indem für sie andere Methoden gewählt werden, die nicht mit dem Ausgangsconstraint kollidieren. Diese neu gewählten Methoden können wiederum in KonÄikt zu anderen Constraints stehen, für die dann neue Methoden gewählt werden, so dafl eine Kette von Constraints mit neu gewählten Methoden entsteht.

Dies geht im Detail folgendermaflen: Anfangs besteht die Kette nur aus dem Anfangsconstraint (AC). Constraints, die dazu in KonÄikt stehen, werden aufgehoben und in die Kette eingereiht. Dabei werden Constraints, die gleich oder stärker als der AC sind, wieder erfüllt, indem für sie andere Methoden gewählt werden, die mit keinem Constraint der Kette kollidieren. Hierbei können durch KonÄikte weitere Constraints die Kette verlängern. Konnten auf diese Weise alle stärkeren Constraints in der Kette erfüllt werden, ist der AC erfüllbar und der Methodengraph kann entsprechend angepaflt werden.

Sollte beim Verfolgen der Kette für einen Constraint keine Methode wählbar sein, die mit der gesamten Kette kollisionsfrei ist, erfolgt ein Backtracking- Schritt: Der Erfüllungsvorgang wird schrittweise zurückgenommen, bis für einen Constraint eine andere Methode gewählt werden kann, mit der dann weiterverzweigt wird. Sollte keine konÄiktfreie Kette möglich sein, kann der Ausgangsconstraint nicht erfüllt werden, der Methodengraph bleibt unverändert.

In Abbildung 2.7(a) ist der Methodengraph zum Beispiel aus Abschnitt 2.1.3.2 zu sehen. Der starke Constraint C2 ist nicht erfüllt (dargestellt durch die gestrichelten Linien) und soll eingeplant werden. Dies kann geschehen, indem C3 zunächst aufgehoben wird. Damit kann C2 die Variable V2 bestimmen (V1 ist hierfür die Eingabe), siehe Abbildung 2.7(b). Da aber C3 stärker ist, mufl dieser seinerseits wieder erfüllt werden. Dies kann geschehen, indem C4 aufler Kraft gesetzt wird. Da es für C4 keine alternative Methode gibt, und C2 stärker ist als C4, ist in Abbildung 2.7(c) ein optimaler Methodengraph erreicht.

Ebenso wäre es im ersten Schritt möglich gewesen, C1 aufzuheben und zum optimalen Graphen 2.7(d) zu gelangen. In beiden Fällen ist ein Constraint der Stärke 1 nicht erfüllt, im Vergleich zu 3 im Ausgangsgraphen (a).

Worst case: exponentielle Laufzeit Da das allgemeine CSP NP-hart ist (siehe Abschnitt 2.1.7), liegt die Vermutung nahe, dafl auch das hier vorgestellte

Seite 20: vorherige Seite | nächste Seite | Übersicht