Tragisches Wetter draus. Ich verstehe sehr gut, wenn man liegen bleiben will, aber ich

bin froh, dass so viele von Ihnen gekommen sind. Okay, ein kleiner Nachtrag. Ich habe

eine schöne Website gefunden. Na, das tut es noch nicht. Also ich bin ganz begeistert.

Ich hatte ja bei der letzten Vorlesung meinen Klicker runtergeschmissen und dann tat er

nicht mehr und am nächsten Tag hat er plötzlich einfach so wieder getan. Also das ist großartig.

Leider kann ich mir jetzt keinen neuen kaufen. Mit einem schönen grünen Leser. Also wir

müssen mit diesem hier auskommen. Wenn man mal ein Gefühl dafür kriegen will, wie das

mit der Suche ist, dann kann man sich mal dieses hier angucken. Das gucken wir uns gleich mal

gemeinsam an. Aber dieses Bild hier, was ein bisschen elaborierter ist als was wir jetzt

mal gleich gemeinsam als Experiment machen, zeigt hier unseren A-Stern Fahrtsuch-Algorithmus.

Wir wollen von hier nach da und haben was wie eine Manhattan Distanz und haben natürlich

diese ganzen Probleme hier drin, sodass wir nicht gerade ausgehen können. Und das interessante

ist, wenn man sich hier mal anguckt, was wie der abgegraste Bereich aussieht eines A-Sterns,

dann sieht man, dass man hier irgendwie so eine seltsame Fläche hat. Und wenn man das

sagen würde, wenn man mal mit Breitensuche vergleichen würde, bei Breitensuche wäre

der abgegraste Bereich rund. Oder zumindest rund modulo Mäuerchen. Und hier sehen wir

doch, dass das irgendwie eine Domänen spezifische Struktur hat. Man guckt mal eben so den Gang

lang und man guckt sozusagen in jeden Raum mal rein und findet dann hinterher letztlich

ein Ziel. Das ist was Heuristiken uns geben und A-Stern uns geben. Greedy Search würde

hier auch sehr gut funktionieren, aber das gucken wir uns an. Und dieses Pfadfinden,

ich muss das mal etwas, das ist diese Webfaltstückchen JavaScript, da kann man irgendwelche Hindernisse

bauen. Machen wir mal irgendwie sowas, man kann den Start machen und sagen wir mal ein

Ziel machen und jetzt kann man verschiedene Suchealgorithmen machen. Ich fange mal mit

Iterative Deepening an und man sieht, das Ding geht mit Tiefensuche los und hat hier eine

ganze Menge Spaß in der Gegend. Es kommt nicht nur mit Kurve, warum nicht? Weil hier ist

der momentane Cutoff. Ich habe das gestern mal ein paar Stunden laufen lassen und bei

einem ganz ähnlichen Problem war es nach Stunden immer noch, hatte es in der Gegend

Spaß, ab und zu mal hat es sich dann bis nach da hin verlaufen und so weiter. Also dem kann

man jetzt eine ganze Weile lang zugucken, das wollen wir jetzt mal nicht machen. Man

kann auch einfach A-Stern machen und Bombs. Beides hat irgendwie eine Manhattan Distanz

als Heuristik gehabt und hier sehen wir ganz deutlich, dass der Suchraum im Wesentlichen

gerade diese F-Konturen sind. Man hat einen Suchraum, der sich im Wesentlichen dem Pfad,

den man hinterher finden wird, anschlängelt und je nachdem, wie viel man sich verschätzt

in der Distanz, hier in diesem Fall Manhattan, so breit sind hier die nutzlos durchsuchten

Dinge. Ich finde das ein ganz hübsches Ding. Man kann damit sehr viel Energie verbrennen,

wenn man Deepening oder sogar Breitensuche macht oder so etwas. Man kann so ein bisschen

für die Suchräume ein Gefühl bekommen. Genau, Nachtrag zur ersten Woche. Okay, wir haben

uns im Wesentlichen beim letzten Mal mit lokaler Suche beschäftigt. Lokaler Suche für Situationen,

wo die systematische Suche, wie wir es gesehen haben, das war ganz schön zu sehen bei der

Interative Deepening Search hier, das ist sehr systematisch. Sonst heißt es immer so

ein Gezucke, macht immer im Wesentlichen das Gleiche, nur hat man sich da irgendwo ein

Block am Anfang verschoben und ganz systematisch wird der gesamte Suchraum durchgesucht und

egal ob man schon weiß, dass man da sicherlich keine Lösung zu erwarten hat, dann wird er

trotzdem systematisch abgesucht. Lokale Suche macht das Ganze anders, es geht im Wesentlichen

darum, dass man unsystematisch sucht, aber dadurch durch das unsystematische Suchen

tiefer in den Suchraum absteigen kann. Und wenn man das gut macht, dann findet man Lösungen

sonst eben nicht. Typischerweise, typischer Art von Problemen sind sowas wie das Dampenproblem,

hatten wir uns angeguckt und die Idee ist, dass man dann solche Hillclimbing Algorithmen

erinnert, indem man irgendwie heuristisch oder auch weniger heuristisch die Zustände evaluiert.

In diesem Fall hatten wir uns angeguckt, wie viele Attacken möglich sind zwischen den