Wir haben uns das letzte Mal damit beschäftigt die Constraint Satisfaction Probleme.

abzuschließen und sind übergegangen zu ersten G-Versuchen in Richtung Logik.

Constraints Satisfaction Probleme sind eine Klasse von Problemen, die sich durch Suche lösen lassen,

aber in denen man so eine Art Grey Box Modulierung der Zustände hat.

Man hat nämlich ein Konfigurationsproblem, das man beschreiben kann, dadurch, dass man Variablen hat,

die gewisse Werte bekommen und weiterhin hat man Constraints.

Die Constraints sind einfach Relationen.

Es gibt da allgemeine Methoden und wir haben uns angeguckt, wie wir aus dieser zusätzlichen Information,

dass man nämlich diese Variablenbelegungsprobleme hat, wie man daraus Heuristiken bauen kann,

die uns zu Effizienz in der Suche verhelfen.

Sehr häufig ist es sogar so, dass wir für einige Probleme mit Inferenzmethoden ganz auf Suche verzichten können.

Wir erinnern uns, es ging dabei um a-zykliche Constraint Graphen,

in denen man einfach durch so eine topologische Sortierungstrick suchfrei mit Forward Checking immer weiter kommt.

Wenn man also ein Problem als Constraint Satisfaction Problem formulieren kann,

dann kann man das mit diesen Methoden angreifen.

Und das Schönste ist natürlich, dass wir Standardsysteme haben, die sind einen Download weit weg,

die haben auch eine einigermaßen sozial verträgliche Syntax und dann braucht man das Problem nur aufzuschreiben.

Und in fast allen Fällen wird das Problem relativ schnell gelöst,

wobei relativ schnell so etwas wie Millisekunden typischerweise ist.

Alle diese KI-Probleme haben die Eigenschaft, dass wenn sie gelöst werden können, werden sie meistens recht schnell gelöst.

Und wenn wir sie nicht hinkriegen, wissen wir nicht, weil es dann praktisch billig lange dauert.

Alles, was wir erwarten würden, wenn wir exponentielle Suche machen.

Die Themen, die uns dabei interessiert haben, waren im Wesentlichen Backtracking-Suche,

die wir möglichst haben versuchen wollen zu vermeiden mit Inferenzmethoden.

Und die Inferenzmethoden, die wir uns angeguckt haben beim letzten Mal, waren einmal Forward-Checking und allgemeiner Kantenkonsistent.

Und dann hatten wir uns zuletzt noch damit beschäftigt, wie man nicht-artzykliche Graphen möglichst schlau in artzykliche Graphen verwandelt

und über diese Schnittmengen-Methode gestolpert, wo man sich anguckt, dass man optimiert irgendwelche solche Schnitte ansetzt, sodass der Rest eben einfach so ist.

Und hier in dieser Sache, da steckt wieder die AMP-Vorschlüssigkeit mit drin.

Gut, da hatten wir uns noch kurz überlegt, wie man das Ganze mit Local Search machen kann.

Und das war's eigentlich.

Das Ganze ist ein großes Feld. Man kann ohne Weiteres eine vierstündige Vorlesung mindestens ein Semester darüber halten,

wie eigentlich alle dieser Themen, die wir hier behandeln, kapitelweise, sind Themen, in denen aktive Forschung gemacht wird,

die für einen speziellen Anwendungsfall tatsächlich benutzt werden und wo dann eben immer mal wieder Anwendungsoptimierungen,

da sind aber auch noch weitere Fragen, gelöst werden müssen.

Gut, was wir jetzt machen wollen, ist eine weitere Folge der Schritte, wo wir mehr aussagen könnten über unsere Probleme.

Das Beispiel, was ich am letzten Mal benutzt habe, war, dass wir in den Constraint-Satisfaction-Problemen einerseits

auf Variablenbelegungsprobleme beschränkt sind, das ist keine große Beschränkung, muss man sagen,

aber andererseits über die Constraints selber keine Inferenz machen können.

Wir können irgendwie die Constraint-Grafen massieren und all solche Sachen, aber wir können nicht die Eigenschaften der Constraints untereinander ausnutzen.

Ein Kardinalbeispiel ist, wenn wir Gleichheits-Constraint haben, wissen wir nicht, dass Gleichheit transitiv ist.

Wir wüssten es schon, aber die allgemeinen Methoden nutzen das nicht aus, weil Constraints Black-Fox ist.

Das sind einfach Relationen, die wie ein Orakel funktionieren, man kann in alle diesen Algorithmen, die wir uns da angeguckt haben,

gucken wir nie in die Constraints rein, wir testen nur auf die Constraints.

Gibt es einen Wert, der in den Constraints zu einem gegebenen Wert liegt, zum Beispiel beim Forward-Check, bei der Kantenkonsistenz.

Das nächste, was wir machen wollen, ist, dass wir Inferenz auf diesen Relationen, auf Constraints und auf allgemeinere Constraints zulassen.

Und da kommen wir dann in das Gebiet der Logik.

Und wir haben uns dann, habe ich versucht vorzustellen, das allgemeine Setup von Logiken.

Mir ist wichtig dabei, obwohl wir nur zwei Logiken kennenlernen werden, hier explizit,

dass Sie verstehen, dass Logiken einfach nur Sprachen sind.

Sprachen mit einem Inferenzsystem und einer Symantik, die wir für jedes Problem bauen können und verwenden können.