Das war's für heute.

Ich wünsche euch einen schönen Abend.

Ich bin gebeten worden, meinen Laserpointer nur auf einen der beiden Schirme zu richten.

Wir nehmen den da.

Es scheint sonst zu viel zu sein, zu koordinieren, aufzupassen, zu verstehen und sich auch noch verschiedenlich umzudrehen.

Okay, kann ich machen. Kein Problem.

Wir haben uns in der letzten Woche mit Constraint Satisfaction Problemen beschäftigt.

Wir haben zwei Varianten gemacht. Einmal Suche mit Horistiken und das Thema, was wir das letzte Mal behandelt haben, war Suche mit Inferenz.

Die Idee hierbei ist, unsere Zustände werden durch eine Nicht-Blackbox beschrieben.

Das eröffnet uns die Möglichkeit, Zustandsbeschreibungen in eine vernünftige Form zu massieren, in der sie weniger partielle Lösungen zulassen und wo wir weniger Suche haben.

Das ist, was sie bei Sudoku machen. Die beiden wichtigen Begriffe hier sind einmal die Äquivalenz von Constraints Networks.

Das ist ganz einfach, wenn sie die gleichen Lösungen zulassen.

Schärfe von Formulierung, Schärfe heißt weniger partielle Lösungen zulassen.

Wir formulieren das im Wesentlichen darin, dass wir mehr Constraints haben.

Die Idee bei der Inferenz ist, dass man schärfer formuliert, man massiert die Probleme in eine Formulierung, die weniger Suche zulässt.

Das gibt große Ersparnisse bei der Suche, wenn man es richtig macht.

Wir haben uns den Algorithmus um Inferenz erweitert.

Im Prinzip ist das das Gleiche wie bisher, nur dass wir diese eine Zeile zusätzlich haben.

Wir erlauben uns, wenn wir einen Suchschritt gemacht haben, in einem Inferenzschritt, das vorhandene Problem schärfer zu formulieren und dadurch zusätzliche Suche zu sparen.

Wir haben uns zwei Verfahren angeguckt. Wir haben uns einmal der Inferenz und Forward Checking angeguckt.

Das ist ganz einfach. Wann immer wir eine Entscheidung treffen, eine Variable zu belegen, dann schieben wir über die Constraints, die von dieser Variable ausgehen, die Information weiter vorwärts und sehen zu, was das für die Domänenreduktion uns gibt.

In diesem Fall sieht man hier, dass diese Entscheidungen vorwärts Konsequenzen haben und wir dadurch Suche sparen.

Dabei ist wichtig, dass wir Soundness haben. Soundness in diesem Zusammenhang heißt, dass wir äquivalente Probleme haben und offensichtlich war ist Forward Checking Sound.

Und natürlich Forward Checking ist sehr, sehr preiswert. Das heißt, wir sollten es machen, wann immer wir können, es sei denn, wir haben noch eine bessere Methode.

Und es gibt tatsächlich eine bessere Methode, nämlich die nennt sich Kantenkonsistenz. Kantenkonsistenz heißt, dass wir nicht nur vorwärts über die Kanteninformation propagieren, sondern auch rückwärts.

Immerhin sind die Kanten symmetrisch und das heißt, wir stellen Situationen her, in denen die Domänen an den beiden Seiten der Constraints konsistent sind.

Das heißt, dass es zu jedem Element in der Ausgangsdomäne ein Element gibt in der Zieldomäne, der das konsistent war.

Und bei der Symmetrie natürlich rückwärts auch. Und das gibt uns tatsächlich mehr Information aus Forward Checking.

Und dieses Beispiel, was wir da oben sehen, war eines, in dem das auch zum Fragen kommt.

Wir haben also eine Verallgemeinerung des Begriffs und haben uns dann mehrere Algorithmen angeguckt, in denen wir diese Kantenkonsistenz sicherstellen können.

Das erste Teilalgorithmus war dieser Revise Algorithmus, in dem wir im Wesentlichen für ein Paar die Information nach vorne schieben.

Das ist im Wesentlichen dasselbe wie Forward Checking. Läuft in K², wenn K die Domänengröße ist.

Und wir haben uns dann darauf aufbauend einen Algorithmus AC1 angeguckt, der im Wesentlichen diesen Revise Algorithmus in beide Richtungen angewandt hat, bis man einen Fixpunkt hat.

Denn jedes Mal, wenn sich was ändert, kann es zu neuen Ersparnissen kommen und deswegen müssen wir diesen Fixpunkt erzeugen.

Und wir haben uns angeguckt, eine Variante dieser ganzen Sache, der sich im Wesentlichen merkt, dass man nichts doppelt berechnet, indem man eine Menge der potenziell geänderten Kanten hat,

der das Ganze im Wesentlichen um einen Faktor von, was war das, m schneller kam.

Als Hausaufgabe werden wir Ihnen die Gelegenheit geben, sich die ganzen Sachen noch einmal vor Augen zu führen.

Mit Backtracking, mit Forward Checking, mit AC3, mit alledem. Und das für ein ganz kleines Problem mal von Hand durchzuspielen.

Einfach nur damit Sie so ein Gefühl dafür kriegen.

Okay, wir haben uns das angeguckt und hatten uns die Runtime dieser ganzen Sache angeguckt und haben da m mal k hoch drei.

Das Wichtige daran ist, dass wir polynomial sind. Insgesamt ist natürlich Constraints Satisfaction, wie wir uns überzeugt hatten, NP vollständig.

Und wir haben hier einen Teil Algorithmus der Inferenz, der polynomial ist und zwar mit einem ziemlich kleinen, also hier Gesamtfaktor,

vier Faktor. Das heißt, das ist eine Sache, die sich in der Praxis sehr stark lohnt.

Okay, irgendwelche Fragen hierzu? Gut, die nächste Idee in der Inferenz war, dass man die Struktur der Probleme in Betracht zieht und stellte sich heraus,

dass wir, wenn wir uns die Grafstruktur angucken, dass man einerseits für jede Teil Komponente eines nicht zusammenhängenden Grafen,

dass man die gesondert betrachten kann. Und dann hatten wir eine Methode gesehen, indem wir erzügliche Constraint Grafen in einem Algorithmus behandelt,

der kein Backtracking braucht. Das ist das Beste, was man hinkriegen kann, wenn man Inferenz macht, dass man in der Such Komponente des Algorithmus,

die ja immer im Hintergrund war, dass man da Backtracking total vermeidet. Und wir können das für einen a-zyklichen Grafen,

weil wir im Wesentlichen dadurch eine Ordnung bekommen, die wir dann abarbeiten mit Forward-Checking. Wir brauchen noch nicht mal Kantenkonsistenz dafür.

Und es stellt sich heraus, dass man hier nicht Backtracking muss. Das heißt, das sind wirklich Constraint-Satisfaction-Probleme, die sehr einfach sind.