Probleme mit Rand- und Nebenbedingungen

Überblick

• Probleme mit Rand- und Nebenbedingungen

• = Constraint Satisfaction Problems (CSPs)

• Backtracking-Suche für CSPs

• Lokale Suche für CSPs

Probleme mit Rand- und Nebenbedingungen (CSPs)

• Standard-Suchproblem:– Zustand ist "black box“: Beliebige Daten, es sind nur Nachfolgerfunktion,

Heuristikfunktion und Zieltest bekannt.

• CSP:– Zustand ist definiert durch Variable X1 … Xn , wobei Xi Werte aus der

Wertmenge („Domaine“) Di annehmen kann.– Zieltest ist eine Menge von Bedingungen (Constraints) C1 … Cm. Jedes Ci

definiert für eine Teilmenge der Variablen Kombinationen zulässiger Werte.

– Lösung ist die konsistente Zuweisung von Werten aus den Domänen Ci an alle Variable Xi.

• Konsistent bedeutet dabei mit den Contraints Ci verträglich.

• Simples Beispiel einer formal representation language

• Erlaubt Gebrauch von general-purpose Algorithmen, die weiten Anwendungsbereich haben, aber dennoch leistungsfähiger als Standard-Suchalgorithmen sind.

•

Beispiel: Karte einfärben

• Variable: WA, NT, Q, NSW, V, SA, T • Domänen Di = {rot, grün, blau} (für alle Variable)• Bedingungen: Benachbarte Regionen müssen verschiedene

Farben haben• Z.B. WA ≠ NT• Oder: (WA,NT) in {(rot, grün), (rot, blau), (grün, rot), (grün, blau),

(blau, rot), (blau, grün)}

Beispiel: Karte einfärben

• Lösungen sind vollständige und konsistente Wertezuweisungen

• Z.B. WA = rot, NT = grün, Q = rot, NSW = grün, V = rot, SA = blau,T = grün.

Constraint-Graphen

• Binäres CSP: Jeder Bedingung setzt zwei Variable in Beziehung zueinander

• Constraint-Graph: – Knoten sind Variable– Kanten sind Bedingungen

–

Klassifizierung von CSPs• Diskrete Variable:

– Finite Domänen:• n Variable, maximale Domänengröße d O(dn) vollständige

Wertezuweisungen• Spezialfall Boolsche CSPs (Domäne {True, False})

– Infinite Domänen:• Integer-Variable, Zeichenketten etc.• Z.B. Auftrags-Scheduling, Variable sind Beginn / Ende für jeden

Auftrag, Werte sind Tage• Auflistung erlaubter Wertekombinationen unmöglich

„Beschränkungssprache“ erforderlich, z.B. StartJob1 + 5 ≤ StartJob3

• Kontinuierliche Variable– Z.B. Beginn / Ende der Nutzung einer Maschine mit

„kontinuierlicher“ Zeit– Lineare Programmierung löst Probleme mit Bedingungen in

Gestalt linearer Ungleichungen (konvexer Bereich) in polynomialer Zeit in n.

•

•

Klassifizierung von Bedingungen

• Unäre Bedingungen betreffen jeweils nur eine Variable– Z.B. SA ≠ grün

• Binäre Bedingungen betreffen Paare von Variablen– Z.B. SA ≠ WA

• Bedingungen höherer Ordnung betreffen 3 oder mehr Variable– Z.B. Kryptoarithmetische Spalten-Bedingungen

–––

Beispiel: Kryptoarithmetik

• Variable: F, T, U, W, R, O• Hilfsvariable für Übertrag: X1, X2, X3

• Domänen: {0,1,2,3,4,5,6,7,8,9}• Bedingungen:

– Alldiff (F,T,U,W,R,O) (alle verschieden)– O + O = R + 10 · X1

– X1 + W + W = U + 10 · X2

– X2 + T + T = O + 10 · X3

– X3 = F, T ≠ 0, F ≠ 0

–––

–

Reale CSPs

• Zuweisungsprobleme– Welcher Lehrer unterrichtet welche Klasse?

• Stundenplan:– Welche Vorlesung wann und wo?

• Planung von Transportaufgaben– Welcher Fahrer, welcher Lastwagen (wieviel Ladung),

welche Strecke? • Planung von Produktionsabläufen

• Viele Realweltprobleme enthalten reellwertige Variable!

•

Formulierung als Standardsuche (inkrementell)

Zustände sind definiert durch bisher zugewiesene Werte.

• Startzustand: Leere Zuweisung { } (keine Variable hat Wert)

• Nachfolgerfunktion: Weise einer noch nicht belegten Variablen einen Wert zu, so dass kein Konflikt mit den schon erfolgten Zuweisungen entsteht. Falls unmöglich: Failure

• Pfadkosten: Konstant

• Zieltest: Die Zuweisung ist vollständig.

•

Eigenschaften der naiven Standardsuche für CSPs

• Standardisiert: Für alle CSPs gleich

• Für n Variable erscheint jede Lösung bei Tiefe n. Verwende Tiefensuche

• Pfad ist irrelevant Alternativ kann auch complete-state Formulierung verwendet werden:

• Zustand = Vollständige Zuweisung (egal ob Bed. erfüllt)• Verwende lokale Suche

• Für n Variable mit d verschiedenen Werten:– b = n d bei Tiefe 0– b(s) = (n - s)d bei Tiefe s– Daher n! · dn Blattknoten bei nur dn möglichen Zuweisungen !

Backtracking Suche: Motivation

• Problem des naiven Ansatzes: n! · dn Blattknoten bei nur dn möglichen Zuweisungen

• Aber: Variablen-Zuweisungen sind kommutativ, d.h.[ WA = rot, dann NT = grün ] ist dasselbe wie[ NT = grün, dann WA = rot ].n! resultiert also aus der (noch vollständig repräsentierten)

Kombinatorik

• Daher Breitensuche unsinnig

• Besser: Tiefensuche

Backtracking Suche• Tiefensuche für CSPs heißt Backtracking Suche, wobei

• nur eine Zuweisung pro Knoten erfolgt b = d (bei d Werten),• falls keine erlaubten Werte vorhanden: Zurück gehen.

• Backtracking ist Standardalgorithmus für uninformierte Suche bei CSPs

• Löst n-Damen bis n ≈ 25

Backtracking: Beispiel

Backtracking: Beispiel

Backtracking: Beispiel

Backtracking: Beispiel

Backtracking: Verbesserungen

• Uninformierte Suche konnte durch problemspezifische Heuristikfunktionen verbessert werden ( informierte Suche)

• Bei CSP steckt bereits in den Bedingungen C etwas problemspezifisches Wissen.

Backtracking kann durch general-purpose (nicht problemspezifische) Methoden erheblich verbessert werden.

• Verbesserungsansätze, basierend auf constraints:1. Welche Variable erhält nächsten Wert?2. In welcher Reihenfolge werden Werte durchprobiert?3. Kann Sackgasse vorhergesagt werden?

4.

–

Variablenauswahl: Minimum remaining values (MRV)

• Heuristik der „am stärksten eingeschränkten Variablen“

• D.h. wähle Variable mit den wenigsten zulässigen Werten

• Dadurch ggf. frühes Abbrechen• Extremfall: Wähle Variable ohne zulässige

Werte Abbruch

•

Variablenauswahl: Most constraining variable

• „Gradheuristik“: Schränke Verzweigungsgrad b ein …

• … durch Wahl der Variablen, die in den meisten Ci noch nicht zugewiesener Variabler enthalten ist.

• Bsp. Landkarte: Entscheidet u.a. auch welche Region als erste eingefärbt wird (im Gegensatz zu MRV)

Werteauswahl: Least constraining value

• Heuristik des geringst-einschränkenden Wertes• D.h. wähle für geg. Variable den Wert, der am

wenigsten Werte für die noch nicht belegten Variablen ausschließt.

• Kombination MRV + least constraining value: 1000-Damen möglich.

•

Sackgasse vorhersagen: Forward Checking

• „Vorabüberprüfung“• Idee:

– Beobachte Wertevorrat für noch nicht belegte Variable.– Beende Suche, wenn eine Variable keine zulässigen Werte mehr hat.

Sackgasse vorhersagen: Forward Checking

• „Vorabüberprüfung“• Idee:

– Beobachte Wertevorrat für noch nicht belegte Variable.– Beende Suche, wenn eine Variable keine zulässigen Werte mehr hat.

Sackgasse vorhersagen: Forward Checking

• „Vorabüberprüfung“• Idee:

– Beobachte Wertevorrat für noch nicht belegte Variable.– Beende Suche, wenn eine Variable keine zulässigen Werte mehr hat.

Sackgasse vorhersagen: Forward Checking

• „Vorabüberprüfung“• Idee:

– Beobachte Wertevorrat für noch nicht belegte Variable.– Beende Suche, wenn eine Variable keine zulässigen Werte mehr hat.

Sackgasse vorhersagen: Constraint Propagation

• „Beschränkungsweitergabe“• Forward checking nutzt Information aus erfolgten Zuweisungen um

noch nicht zugewiesene Variable zu checken.• Aber nicht alle Sackgassen werden früh erkannt:

• NT und SA können nicht beide blau sein!• Idee: Folgen der Beschränkungen einer Variablen noch weiter in die

Zukunft propagieren• Constraint Propagation erzwingt wiederholt Bedingungen lokal• Algorithmen für Constraint Propagation ?

Constraint Propagation:Arc consistency

• Einfachste Form der Constraint Propagation: „Kantenkonsistenz“

• Gerichtete Kante X Y ist konsistent, wenn es für jeden Wert x aus X ein zulässiges y aus Y gibt, das mit x verträglich ist.

• Konsistenz von X Y kann hergestellt werden, indem alle Werte aus X entfernt werden, für die es kein zulässiges y aus Y gibt, das mit x verträglich ist.

• Idee: Beschränke Wertevorrat durch Herstellung von Kantenkonsistenz!

• Wenn X einen Wert verliert, müssen die Nachbarn von X wieder überprüft werden.

• Arc consistency erkennt Sackgassen früher als forward checking.

Constraint Propagation:Arc consistency

Constraint Propagation:Arc consistency

Constraint Propagation:Arc consistency

Constraint Propagation:Arc consistency

• Stellt Kantenkonsistenz her

• Funktion Rm-Inconsistent-ValuesRm-Inconsistent-Values (Xi, Xj) :– Checkt ob für jedes x in Xi passendes y in Xj

– Falls nicht, entferne x aus Xi – Falls ein x aus Xi entfernt wurde, return True, sonst False

• Funktion AC-3AC-3(csp) :– Lege Schlange von Kanten (Xi, Xj) an– Arbeite Schlange ab mit Rm-Inconsistent-ValuesRm-Inconsistent-Values– Falls dabei Rm-Inconsistent-Values Rm-Inconsistent-Values True zurückgibt:

• Reihe alle „Nachbarn“ in Schlange ein

Kantenkonsistenz-Algorithmus AC-3

Kantenkonsistenz-Algorithmus AC-3

Zeitkomplexität: O(n2d3), da• Schlangenlänge: n2 Kanten, jede Kante d Mal in Schlange• Rm-Inconsistent-Values: Rm-Inconsistent-Values: O(d2)

Lokale Suche für CSPs• Hill-Climbing und simulated annealing bearbeiten meist

„vollständige“ Zustände, d.h. alle Variablen sind zugewiesen.

• Anwendung auf CSPs:– Erlaube Zustände mit nicht erfüllten Bedingungen– Operatoren verändern Werte

• Variablenauswahl: Zufällige Wahl aus Menge der Variablen mit Konflikten.

• Wertauswahl durch Heuristik minimaler Konflikte (Min-Conflicts) :– Wähle den Wert, der am wenigsten Bedingungen verletzt– D.h. Hill-Climbing mit h(n) = Gesamtzahl verletzter Bedingungen

–

–••

–

–•

•

Beispiel: 4-Damen• Zustände: 4 Damen in 4 Spalten (44 = 256 Zustände)• Aktionen: Bewege Dame in Spalte• Zieltest: Keine Bedrohung• Evaluationsfunktion: h(n) = # Bedrohungen

• Kann aus zufälligem Anfangszustand n-Damen in nahezu konstanter Zeit für bel. n mit hoher Wahrscheinlichkeit lösen

(z.B. n = 10,000,000)

••

•

Problemstruktur• Idee: Nutze Problemstruktur (repräsentiert in Constraint-Graph) zur

Beschleunigung.• Welche Eigenschaften des Constraint-Graphen sind nützlich?• Bsp.: Tasmanien unverbunden! Suche nach unverbundenen (=unabhängigen) Unterproblemen!• Bsp.:

– n Variable, Domänengröße d– Zwei Teilprobleme der Größe k + l = n– Aufwand O(dk + dl) statt O(dn) !

Baumstruktur

• Constraint-Graph = Baum, d.h. jedes Paar von Variablen durch höchstens einen Pfad verbunden

• Algorithmus mit Aufwand O(nd2):1. Wurzel = bel. Variable.2. Ordne Variable linear, so dass stets Elternknoten vor

Kindknoten jede Variable hat genau einen Vorgänger (außer Wurzel).

3. Benenne geordnete Variable neu X1… Xn .4. For j=n to 2

Kantenkonsistenz (Xi, Xj) herstellen, wobei Xj Kind von Xi.

5. Weise X1 erlaubten Wert zu.6. For j=2 to n

Weise Xi einen mit dem Elternknoten verträglichen Wert zu.

Baumstruktur

Graph-Reduktion auf Baum

• Kann allg. Constraint-Graph auf Baum reduziert werden?

• Zwei Ansätze:1. Knoten „löschen“:

Belege einige Knoten mit Werten, so dass restliche Knoten Baum bilden

2. Knoten zusammenlegen:Zerlege Constraint-Graph in „verbundene Unterprobleme“

1 – Knoten löschen

1 – Knoten löschen

1. Bestimme Knotenmenge S („zyklische Schnittmenge“), nach deren Entfernung der Graph zum Baum wird.

2. Bestimme Menge B(S) aller zulässigen Variablenbelegungen für S.

3. For all b in B(S) :• Konsistenz aller anderen (d.h. nicht in S

enthaltenen) Domänen mit b herstellen.• Baum-Algorithmus auf Restproblem anwenden• Falls Lösung: Fertig.

2 - Baumzerlegung• Zerlege Constraint-Graph in Baum aus

Unterproblemen, so dass– Jede Variable auftritt– Jede Bedingung auftritt– Variable, die in mehreren Unterproblemen auftreten,

dort den gleichen Wert haben

2 - Baumzerlegung

Lösung finden:– Löse Unterprobleme (falls eins unlösbar Ende)– Unterproblem wird „Megavariable“ dessen Domäne

Lösungsmenge des Unterproblems ist– Baum-Algorithmus anwenden

Zusammenfassung

• CSPs sind spezielles Suchproblem:– Zustände sind Werte einer Variablenmenge– Zieltest ist Menge von Bedingungen für Werte der Variablen

• Backtracking = Tiefensuche mit einer Wertzuweisung pro Knoten

• General-purpose Heuristiken zur Variablen- und Wertauswahl sehr effektiv

• Forward Checking verhindert Zuweisungen die garantiert in Sackgasse führen

• Constraint Propagation (z.B. Kantenkonsistenz) hilft Wertauswahl zu beschränken und Inkonsistenzen zu erkennen

• Komplexität des Constraint-Graphen bestimmt Lösungskomplexität. Falls (teilweise) Reduktion auf Baum möglich, erhebliche Vereinfachung

• Lokale Suche mit Min-Conflicts ist in der Praxis hocheffektiv•••••

–

–

•