Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Wir wollen heute über Suche reden und zwar, wir erinnern uns, es geht um allgemeines Problemlösen,

was man übersetzen kann als Problemlösen mit und durch Suche. Die Idee ist dabei, dass man

ein Problem formuliert, indem man es darstellt als eine Menge von Zuständen und unser Standardbeispiel

war hier Reisen in Rumänien. Die Zustände sind einfach das gleiche wie die Städte in Rumänien,

in denen man sein kann und es gibt Operatoren, also Zustandsübergänge, die in diesem Fall hier

einfach der Übergang von Arad nach Sibiu ist, wenn man da in einem Zug hin kann, aber nicht von Arad

nach Krajowa. Wenn man nach Krajowa will oder eben nach Bukarest, dann muss man mehrere Operatoren

machen und im Wesentlichen ist eine Lösung dieses Problems nichts anderes als eine Verkettung von

Operatoren, um von einem Initialen Zustand in einen Zuhlzustand zu kommen. Das sind unsere vier Dinge,

die wir brauchen. Das eine ist, wir haben eine Menge von Zuständen, wir haben eine Menge von

Zustandsübergängen, wir haben einen Initialen Zustand und wir haben eine Menge von Zielzuständen.

Wenn wir ein Problem so darstellen können, dann haben wir schon etwas eingeschränkt über die

Arten von Problemen, die wir lösen können. Wir haben einfach dadurch, dass wir sagen,

wir haben einen Initialen Zustand, haben wir eine vollobservable Welt. Wir müssen zumindest sehen

können, wir sind ein Arad. Das heißt, alle Real-World-Probleme, ich habe Stress mit meinen

Eltern oder so etwas, sind sozusagen außen vor, weil ich unter Umständen gar nicht weiß,

in genau was für ein Initialer Zustand das ist. Meistens, wenn ich zum Beispiel Stress mit meinen

Eltern habe, dann weiß ich gar nicht so richtig, was falsch ist, was die schon wieder wollen und so.

Das ist sozusagen der Raum, in dem wir uns bewegen. Die andere Sache ist, dass wir Zustandsübergänge

haben, die sind deterministisch. Wir bewegen uns irgendwie in einer deterministischen Welt. Aber

wenn das alles so ist, dann können wir unter Umständen, wenn wir schlau genug sind und kreativ

genug sind, irgendwie eine Menge von Zuständen erfinden und Zustandsübergängen erfinden und

dann können wir solche Probleme formulieren und dann haben wir eine Chance mit diesen

Suchalgorithmen tatsächlich Lösungen zu finden. Wir hatten uns die Mathematik dieser ganzen Sache

angeguckt. Im Wesentlichen brauchen wir für ein Suchproblem, brauchen wir vier Dinge, Zustände,

Operatoren, Initiale und Zielzustände und manchmal gibt es eben auch noch eine Kostenfunktion,

die, man kann sich gleich vorstellen, was das ist. Eine Kostenfunktion könnte sein, wie lange dauert

es oder wie viel kostet mich das oder wie häufig werde ich überfallen oder was weiß ich. Man kann

sich sehr viele Kostenfunktionen vorstellen, je nachdem, was sie optimieren wollen. Ja.

Kann die mehr dimensional sein oder muss man immer auch eine Zerwahlung verbringen?

Nö, die kann mehr dimensional sein, alles was Sie sich vorstellen können. Schön wäre es, wenn man

die addieren könnte in irgendeiner Form. Weil typischerweise ist es so, dass wenn ich, dass ich

die Kosten aufsummieren will, je nach Operatoren, aber alles wo das geht, kein Problem. Typischerweise,

das werden wir noch im nächsten Semester lernen, kann man das aber auch immer alles auf eine

reelle Zahl runterbrechen. Okay, gut. Wir hatten uns unterhalten einmal über Blackbox-Beschreibungen,

sprich die Zustände, die sind einfach, wir stellen die uns hier so vor, dass die einfach, sagen wir mal,

durchnummeriert sind oder benahmt sind oder so was und keine interne Struktur haben. Wir wissen über

den Zustand Arad nichts, außer dass es der Zustand Arad ist. Okay? Und deswegen unterschiedlich ist

von dem Zustand Sibiu. Aber ob Arad eine schöne Stadt ist, die am Fluss gelegen ist oder so etwas

und Sibiu so eine furchtbar schreckliche Bergarbeiterstadt oder so was ist, das wissen wir alles nicht.

Ich weiß es im Übrigen auch nicht. Ich war da noch nie, aber das ist tatsächlich, das ist auch

so ein gutes Beispiel. Ich vermute, dass viele von Ihnen da auch noch nicht gewesen sind. Das heißt,

Sie wissen eigentlich nichts darüber über den Zustand. Das ist genau das, was Sie sich

darüber vorstellen wollen. Und wir werden heute sehen, dass ich in gewisser Weise Sie total in die

Irre geführt habe, indem ich hier diese Karte angeschrieben habe, angezeigt habe, denn Sie wissen

einfach viel zu viel schon über Rumänien durch diese Karte. Und das gibt Ihnen einen unfairem

Vorteil. Aber den werden wir heute ausgleichen, gar kein Problem. Und dann gibt es natürlich noch

irgendwie Zustandsbeschreibungssprachen, wo man Zustände dadurch kriegt, dass man sie beschreibt.

Und dann hätten wir im Termini von vor einer Woche eben eine faktorisierte oder sogar eine