Musik

Guten Morgen. Sie haben am Montag eine Vorlesung über

Suche, also Problemlösen und Suche gehört und Dennis hat mir berichtet, dass die

ganze Mannschaft ziemlich gelangweilt reinguckte und er vermutet, dass, sieht

das alle schon kennen. Kann ich mal nachfragen, wer kannte diese ganzen

Suchalgorithmen und alle sowas schon von Ihnen? Oder eher Gegenprobe, wer kannte

das noch nicht? Teilweise, okay. Wir werden heute mit Suche weitermachen und machen

heuristische Suche. Wer kennt von Ihnen heuristische Suche schon? 1, 2, gut, keiner

ist es so ganz sicher, das ist jetzt schon mal ganz gut. Die nicht heuristische Suche,

also die uninformierte Suche, die wir das letzte Mal gemacht haben, ist auch etwas, das macht

man nur im größten Notfall. Aber die sind natürlich die Grundlage dafür, was man dann

hinterher an Verbesserungen machen kann. Ich möchte kurz nochmal wiederholen, wir haben

erstmal den Boden bereitet für Suche, indem wir uns angeguckt haben, wie formulieren wir

Probleme und die Idee dabei ist, dass man, um diese Klasse von Suchalgorithmen anzuwenden,

dass man Probleme so formuliert, dass sie eine Menge von Zuständen haben, in diesem

Beispiel repräsentiert durch jede rumänische Stadt, in der man sein könnte gerade und

eine Menge von Operatoren. Operatoren, die einen von einem Zustand in den nächsten bringen.

Mathematisch gesehen ist das sehr trivial, das Ganze ist nämlich eigentlich nur ein

Graf einer Relation von Operatoren und von Zuständen. Also eigentlich nichts dahinter,

was man außerdem hat sind irgendwelche Initialzustände, in denen man sein könnte, wenn man das Problem

anfängt und irgendwelche Zielzustände, in denen man rein will. Eine Lösung dann ist

eben eine Kette von Operatoren, die einen von allen, von beliebigen Initialzuständen

in irgendwelche Zielzustände bringt. Nur wenn wir unser Problem so formulieren können,

können wir diese Klasse von Algorithmen auch anwenden. Was man außerdem noch häufig hat,

ist, dass man jedem Operator ein Kosten zuordnet und das werden wir irgendwie mit so einer

Kostenfunktion aufschreiben. Dies hier ist eine Blackbox Beschreibung. Wir haben auch

Whitebox Beschreibungen, das werden wir dann hinterher beim Planen oder so etwas sehen.

Im Moment reichen uns die Blackbox Beschreibungen aus und das ist natürlich zum Programmieren

ganz nett, weil das in gewisser Weise bereits ein API-Versuche ist. Genau, wir haben über

Problemtypen nachgedacht und haben uns einige Beispiele angeguckt. Hier sieht man ganz nett,

dass der Zustandsraum tatsächlich ein Graph ist. Die meisten Zustandsräume sind größer

als man sie einfach aufmalen kann. Diese Klasse von Algorithmen, die wir uninformiert nennen,

das sind nämlich diejenigen, von denen wir nur die Problembeschreibung haben, also das

reine nackte API, kann man lösen durch eine Klasse von Algorithmen, die wir Baumsuchalgorithmen

nennen, die im Wesentlichen einfach den Zustandsraum in einen Graph abwickeln nach einer gewissen

Strategie. Und die einzige Unterschied dabei ist die Strategie. Und die Strategie ändert

sich einfach nur darin, welches wir als den jeweils nächsten Knoten aussuchen. Und dann

kann man sich das angucken. Wir haben immer in jedem Zustand einen Satz von Knoten im

Baum, den wir schon abgearbeitet haben, das heißt wo wir alle Nachfolgerknoten berechnet

haben. Und wir haben immer einen momentan ausgewählten Knoten, den wir als nächstes

expandieren. Und wichtig ist, wir haben diese Menge von Knoten, die wir noch nicht abgearbeitet

haben, aber die wir schon erzeugt haben. Im Englischen heißt es nie French. Und je nachdem,

wie wir in der French den nächsten Knoten aussuchen, kriegen wir eine unterschiedliche

Strategie. Das ist irgendwie so das Paradigma, was wir hier haben. Wobei ganz wichtig ist,

dass wir hier auf einer Baumdatenstruktur arbeiten und nicht direkt auf der Grafdatenstruktur.

Das ist unterschiedlich. Man sieht es daran zum Beispiel, dass hier Knoten auftauchen

im Baum, die mit den gleichen Zuständen gelabelt werden. Das heißt, irgendwie so ein Baumknoten

hat irgendwie folgende Form. Wir haben irgendwie die Baumstruktur und wir haben als Label den

Zustand. Und der Zustand ist das, was wir eigentlich vom Problem gegeben haben. Also

was wir wirklich machen ist, wir wickeln diesen Graf in einen Baum ab. Gut. Bei all diesen