Breitensuche und ihre Anwendungen

Im Einführungs-Tutorial navigierten wir einen Charakter durch ein Labyrinth, um ein Ziel zu erreichen. Im ersten Schritt wurde angenommen, dass das Ziel null Schritte entfernt war. Dann haben wir alle Felder gefunden, die einen Schritt vom Ziel entfernt waren. Dann alle Felder, die zwei Schritte vom Ziel entfernt waren. Dann drei Schritte, und so weiter, bis wir das Ausgangsfeld des Charakters erreichten. Wenn du dir merken könntest, von welchem Feld der Entfernung $k$‍ du gekommen bist um zu einem Feld mit der Entfernung $k+1$‍ zu gelangen, dann könntest du diesen Weg zurückverfolgen, um einen Pfad vom Charakter zum Ziel zu finden.

Hier ist das Bild, das wir im Einführungs-Tutorial gesehen haben:

Wenn du genau hinschaust, dann erkennst du einen ungerichteten Graphen. Jeder Knoten entspricht einem Feld, das nicht Teil einer Wand ist, und jede Kante verbindet benachbarte Felder.

Der Weg, der durch das oben genannte Verfahren gefunden wird, hat eine wichtige Eigenschaft: kein anderer Weg vom Charakter zum Ziel is kürzer. Das liegt daran, weil wir einen Algorithmus namens Breitensuche verwendet haben, um den Weg zu finden. Die Breitensuche, auch bekannt im englischen als breadth-first search (BFS) , findet kürzeste Wege von einem gegebenen Startknoten zu allen anderen Knoten, in Bezug auf die in den Pfaden enthaltenen Kanten.

Hier ist ein weiteres Beispiel für die Breitensuche: das "Sechs Grade von Kevin Bacon" Spiel. Hier versuchen die Spieler, Filmschauspieler und Schauspielerinnen mit Kevin Bacon zu knüpfen, gemäß einer Kette, wer mit wem in einem Film erschienen ist. Diese Kette sollte möglichst kurz sein. Es ist erstaunlich, wie viele Schauspieler und Schauspielerinnen mit Kevin Bacon in einer Kette von sechs oder weniger in Verbindung stehen. Nehmen wir als Beispiel Kate Bell, eine australische Schauspielerin. Sie spielte 2006 im Film MacBeth zusammen mit Nash Edgerton; Edgerton spielte 2003 im Film The Matrix Reloaded zusammen mit mit Laurence Fishburne; und Fishburne spielte im selben Jahr im Film Mystic River mit Kevin Bacon. Deshalb ist Kate Bell's "Kevin Bacon Zahl" 3. Es gibt mehrere Möglichkeiten zu bestimmen, dass Kate Bells Kevin Bacon Zahl 3 ist. Du kannst die Kevin Bacon-Nummer beliebiger Schauspieler- und Schauspielerin auf der Orakel von Bacon Webseite nachschlagen.

Du vermutest vielleicht schon, dass die Orakel von Bacon Webseite einen ungerichteten Graphen enthält, in dem jeder Knoten einem Schauspieler oder Schauspielerin entspricht. Wenn zwei Personen im selben Film spielen, dann gibt es eine Kante, die deren zwei Knoten miteinander verbindet. Eine Breitensuche, beginnend mit dem Knoten von Kevin Bacon, findet den kürzesten Pfad zu allen anderen Schauspielern und Schauspielerinnen.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.