Video 11-5: Tiefensuche (Teil 1)

0:01 Also im nächsten Abschnitt schauen wir uns einen ersten Grafalgorithmus an, der mal bisschen mehr tut, als den Graf mit dem Computer abzulegen und dann schlafen zu gehen. Und das ist die Tiefensuche oder auf Englisch Dep First Search.

0:23 Und man könnte vielleicht sagen, es ist äh mit der älteste Algorithmus auf Grafen, wenn man äh richtig drauf guckt. Und das ist die Frage, wie man aus einem Labyrinth rein und wieder rausfindet. Wenn wir uns ein Labyrinth vorstellen, dann hätten wir vielleicht so ein Gebilde vor Augen. Da gibt's also solche Korridore, durch die ich laufen kann. Da gibt's Abzweigung. Wenn ich mir aber die Frage stelle, welche an welchen Stellen muss ich eine Entscheidung treffen, dann eigentlich nur da, wo es auch eine Verzweigung gibt. Also an all diesen Punkten, wo ich eine Option habe, wo ich weiterlaufen kann, da mache ich einen Knoten und ich verbinde die z.B. diesen Weg hier ist diese Kante, wenn es einen Korridor zwischen diesen zwei Punkten gibt, der diese direkt verbindet. Wenn Sie sich überlegen, ähm das ist ein cooles Labyrinth, gell? Das hat gar keinen Ein oder Ausgang, das heißt, das sind wir eh verloren. Aber angenommen, es gäbe irgendwo einen Eingang und es gäbe irgendwo einen Schatz.

1:32 Das sind zwei Münzen. Ich bin kein Künstler. Was soll wir machen? Äh vielleicht ist es auch der Minotaurus, der in der Mitte des Labyrinths auf Sie wartet. Wenn Sie jetzt die Frage stellen, kann ich von hier nach da kommen und was muss ich dafür tun, wo muss ich links und rechts abbiegen, dann können wir das eigentlich darauf reduzieren, nur an diesen Knotenpunkten, an denen ich eine Abzweigung habe, eine Entscheidung zu treffen, denn auf allen geraden Stücken dazwischen bleibt eh nichts übrig, als einfach zu laufen. Jetzt haben sie sicherlich alle schon mal irgendwie solche Spiele gemacht und sich überlegt, wie man das vielleicht lösen könnte und tatsächlich deswegen ältester Algorithmus ähm ältester Grabalgorithmus an dem die grieche Mythologie enthält die Lösung. Das ist der Ariatnefaden und Tesus äh Abenteuer im Labyrinth des Minotaurus. Weiß nicht, wer wer kennt die griechen sagen dazu? Sagt Ihnen das was oder kennt das niemand? Wer kennt das? Wer hat das noch nie gehört?

2:34 Ja, äh halb halb. Ähm, also die der Rat damals war, da gibt's natürlich noch eine schöne Rundgeschichte. Da gibt's da gibt's ähm Leidenschaft und Liebe und Krieg und all das. Äh, die algorithmische Kurzversion ähm ist, dass äh Tes unser Held, der in das Labyrinthmus einen Tipp bekommt von Ariatne, nämlich er soll sich eine Schnur mitnehmen, die am Eingang festbindet, sodass er, wenn er irgendwo lang läuft, diese Schnur hinter sich abrollen kann und wenn er irgendwo in eine Sackgasse gerätt oder denkt, er kommt nicht mehr weiter, dann kann er der Schnur zurückfolgen. So findet er zumindest immer aus dem Labyrinth wieder raus. Das war äh ihr ihre größte Sorge, was damit nicht sofort klar ist, ob man irgendwie auch sicher zum Ziel kommt. Also sicher, da gab's dann noch dieses Monster, den Minotaurus, aber den das meine ich nicht mit sicher, sondern ähm vielleicht bin ich ja eine Weile gelaufen in eine Sackgasse gerannt und dann habe ich einfach frustriert aufgegeben, meinen Faden eingerollt und gesagt, blöd mit dem Heldenturum, das wird heute nichts. Was sozusagen noch fehlt, wäre eine Kreide oder irgendeine andere Art Wege zu markieren. Hier war ich schon, da nicht noch mal in die Sackgasse laufen oder hier war ich noch nicht, da muss ich vielleicht noch hin.

3:56 Der Teil fehlt in der Mythologie. Ähm insofern vielleicht ein bisschen was algorithmisches noch übrig zum Erkunden. Also erstmal, wie wie geht es mit dem Faden? Und hier ist natürlich ähm in der in der Darstellung so ein ganz kleines bisschen geschummelt, denn sie sehen, dieser Faden dahinter lässt quasi so eine Schleimspur, wo wir erkennen können, wo wir schon waren. Angenommen, hier ist der Eingang, dann können wir unseren Faden hier so ausrollen. Vielleicht biegen wir hier ab, dann kommen wir hier zurück und dann entschließen wir uns, ah, wir gehen wieder zurück, warum auch immer. Und äh dann würden wir hier zurückrollen und dann haben wir hier dieses Stück markiert, aber sind aus diesem Korridor wieder rausgekommen, sind dann woanders abgebogen. Und dann wäre es jetzt hilfreich noch zu wissen, dass wir diesen Teil schon durchsucht haben, damit wir an der anderen Stelle auch wissen, hier war ich noch nicht, da muss ich noch hin und äh na ja, so kann ich eben sukzessive das Labyrinth durchwandern.

4:57 Der Punkt ist mit diesen zwei Dingen zusammen, dem Faden, damit ich den Rückweg finde, wo kam ich her und dem Markieren. Diesen Korridor habe ich schon abmarschiert. Mit diesen beiden Zutaten kann man jedes Labyrinth systematisch durchforschen und hat am Ende das ganze Labyrinth gesehen und noch alle Schätze gefunden, alle Monster aufgescheucht und findet den Weg wieder raus. Das ist dann die beste Lösung, glaube ich, für alle Beteiligen, außer vielleicht für den Minotaurus. Ähm, das ist er wohl, der Minotaurus. Hatte ich mir anders vorgestellt. Da gibt's glaube ich noch andere Bilder von. Und hier ist Claud Shannon, wie er versucht das Labyrinth mit dieser ähm Darstellung zu lösen. Na ja. Äh, also das ist ähm sozusagen dieser alte Algorithmus, der dahinter steckt, die ähm wie man so ein Labyrinth vollständig durchschreiten kann. Und vielleicht zum Abschluss noch, je nachdem wie groß das Labyrinth ist, ist das offensichtlich, dass man irgendwie hier hinkommt, ne? Vielleicht nicht ganz offensichtlich, aber ich komme kann fast ngirgends abbiegen. Das heißt, ich muss einfach irgendwie hier grob langlaufen.

6:25 habe ich zumindest geschafft bei dem ein hier ist easy, da habe ich es hinbekommen. Wenn man das noch ein bisschen größer macht, dann wird's schon um unübersichtlicher und man es noch größer macht, dann möchte man gerne eine computerbasierte Lösung haben. Äh insbesondere gibt's ja sehr viele Abzweigung, die man sich merken muss. äh, dass man da, was ich hier versucht habe, war ja im Wesentlichen niemals einen Rückweg wieder einzuschleichen und man hat mir so ein bisschen vorausgucken, das hier gerade noch hinbekommen. Einmal war es knapp, im allgemeinen funktioniert es nicht. In so einem großen Labyrinth muss der Algorithmus schon einen großen Teil systematisch äh erforschen.

7:11 Okay. Ähm machen wir den soften Teil noch. Wie der Algorithmus im Detail arbeitet, schauen wir uns in Ruhe am Mittwoch an. Ähm, gibt hier noch so einen ähm Metakommentar sozusagen. Wir werden äh für diverse Grafalgorithmen immer das gleiche Designmuster verwenden, dass wir eine extra Klasse haben, die dieses eine Problem löst. Die hat dann einen Konstruktor, in dem man den Graf übergibt und eventuell andere Parameter, die für das Problem nötig sind. Z.B. hier den Eingang vom Labyrinth, wo wir loslaufen und dann äh läuft die eigentliche Arbeit im Konstruktor ab und die Klasse selbst hat dann vielleicht noch Datenstrukturen, um sich Sachen zu merken, so wie wir hier uns merken werden müssen, wo wir lang gelaufen sind. Und dann gibt's Methoden auf diesem Instanz auf der auf dem Objekt, mit dem wir die Antworten zu Fragen äh uns geben lassen können. Z.B. gibt es eine Möglichkeit zu irgendeinem bestimmten Knoten zu kommen von dem Knoten S aus. Und wenn es das gibt, was ist denn die Folge von Knoten, die die ich nehmen muss, um dahinzukommen?

8:16 Das ist immer das ähm das Muster, dass wir verwenden werden. Damit kann man eben die Darstellung vom Graf selbst von den Algorithmen, die auf den Grafen arbeiten, entkoppeln. Und sie können den Graf einmal als Adjazensmatrix oder als Adjazenszliste oder über eine clevere komprimierte Datenstruktur darstellen und den gleichen Grafalgorithmus darauf verwenden oder umgekehrt, sie tauschen Algorithmus gegen was Neues aus und die Grafrepräsentierung muss man nicht anpassen. äh diese Sachen zu entkoppeln ist einfach sehr hilfreich, um ähm implementieren zu können Implementierung flexibel austauschen zu können. Ja.