Manchmal klingen verschiedene Probleme zunächst ganz unterschiedlich, stellen sich aber beim Lösungsversuch als ähnlich heraus. Was haben Pac-Man, die britische Königsfamilie, und eine Autofahrt nach Orlando gemeinsam? Bei allen gibt es Probleme, den Weg zu finden bzw. den Pfad zu suchen.
  • Wie ist der momentane Prinz William mit König William III verwandt, welcher 1693 das College of William and Mary gestiftet hat?
  • Welchem Pfad sollte ein Gespenst folgen, um so schnell wie möglich zu Pac-Man zu gelangen?
  • Was ist der beste Weg, um von Dallas, Texas, nach Orlando, Florida, zu kommen?
Wir brauchen einige Informationen, um all diese Fragen beantworten zu können.
Zum Beispiel würde ein Stammbaum der britischen Königsfamilie Verbindungen zwischen Leuten zeigen, die direkt miteinander verwandt sind. Prinz William ist der Sohn von Charles Philip Arthur Windsor. Charles ist der Sohn von Königin Elizabeth II. Das Problem ist, eine kurze Kette auf dem Stammbaum zu finden, die Prinz William und William III über direkte Verbindungen miteinander verknüpft. Wie du am folgenden Stammbaum sehen kannst, sind einige Verbindungen nötig.
Stammbaum der königlichen Familie mit Elizabeth II und William II hervorgehoben
Für Pac-Man brauchen wir eine Karte des Labyrinths. This map shows connections between adjacent open squares in the maze—or lack of connections, if there is a wall in between—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
Pac-Man-Labyrinth mit einem Monster und Pac-Man hervorgehoben
Um einen Fahrtweg von Dallas nach Orlando zu finden, können wir eine Karte der Vereinigten Staaten benutzen, die Verbindungen, also Straßen, zwischen nebeneinanderliegenden Städten zeigt. Es gibt keine einzelne Straße, die Dallas und Orlando direkt verbindet, aber es gibt eine Abfolge von Straßen.
US-Straßenkarte mit Dallas und Orlando hervorgehoben

Ein Labyrinth erkunden

Schauen wir uns zum Beispiel Pac-Man, ein Computerspiel bei dem die Hauptfigur durch Klicken auf Orte in einem Labyrinth gesteuert wird, mal genauer an. Das Spiel seht ihr unten. Versuche, auf ein paar Orte zu klicken, um die Figur, den gelben Kreis, zum Ziel, dem roten Rechteck, zu bewegen.
Siehst du, wie die Figur zum Ziel bewegt wird? Dafür muss das Programm die genaue Abfolge an Bewegungen bestimmten, der die Figur folgen muss, um dorthin zu gelangen, wo der Nutzer hingeklickt hat, und dann diese Bewegungen animieren. Es gibt manchmal mehrere Pfade, denen der Charakter folgen muss, und dass Programm muss den besten dieser Pfade auswählen.
Bevor es sich für einen Algorithmus entscheidet, muss erst die Bewegung festgelegt werden: die Wände bestehen aus grauen Quadraten und erlaubte Durchgangsorte sind leer. Bei jedem Schritt kann die Figur von einem Quadrat zu einem anliegenden Quadrat springen. Diese Figur kann sich, wie der Turm beim Schach, nicht diagonal bewegen.
Here's the idea behind the algorithm that this program uses: move 1 square closer to the goal—the place the user clicked on—in each step. Aber was bedeutet "näher an das Ziel"? In einer geraden Linie zum Ziel zu wandern wird häufig dazu führen, dass die Figur gegen eine Wand läuft. Der Algorithmus muss also bestimmen, welches der umliegenden Quadrate tatsächlich "näher am Ziel" ist - zum Beispiel durch die Zuweisung von "Kosten" zu jedem Quadrat, was die Mindestanzahl an Schritten repräsentiert, welche die Figur benötigt, um von dieser Ecke ans Ziel zu kommen. Hier ist ein Algorithmus für die Zuweisung von Kosten zu jedem Quadrat:
  1. Beginne am Zielquadrat. Wie weit ist das Ziel vom Ziel entfert? Null Schritte, also markiere das Ziel mit der Zahl 0.
  2. Finde alle Quadrate im Labyrinth die genau einen Schritt vom Ziel entfernt sind. Markiere sie mit der Zahl 1. Wenn in diesem Labyrinth das Ziel das Quadrat für den Ausgang ist, gibt es nur ein Quadrat, das genau einen Schritt entfernt ist.
  3. Jetzt finde alle Quadrate im Labyrinth, die genau zwei Schritte vom Ziel entfernt sind. Diese Quadrate sind einen Schritt von denen entfernt, die mit 1 markiert sind, und wurden noch nicht markiert. Markiere diese Quadrate mit der Zahl 2.
  4. Finde alle Quadrate im Labyrinth, die genau drei Schritte vom Ziel entfernt sind. Diese Quadrate sind einen Schritt von denen entfernt, die mit 2 markiert sind, und wurden noch nicht markiert. Markiere diese Quadrate mit der Zahl 3.
  5. Markiere weiter Quadrate im Labyrinth nach dem zunehmenden Abstand vom Ziel. Nachdem die Quadrate mit der Zahl k gekennzeichnet wurden, markiere alle Quadrate mit der Zahl k, plus, 1, die einen Schritt von den mit k markierten wegliegen und noch nicht markiert wurden.
Am Ende markiert der Algorithmus das Quadrat, auf dem die Figur steht. Das Programm kann dann einen Pfad zum Ziel finden, indem es eine Abfolge von Quadraten vom Start ausgehend so auswählt, dass die Zahlen auf den Quadraten immer weiter abnehmen. Wenn du die Zahl als die Höhe des Quadrats ansiehst, würde es sozusagen immer weiter nach unten gehen.
Du kannst unten mit dem Kostenmarkierungsalgorithmus herumspielen. Klicke auf "Algorithmus neu starten", um von vorn zu beginnen.
Was passiert wenn der Nutzer versucht vom Startquadrat zum Ziel zu kommen? Mit dem Quadratmarkierungsalgorithmus ist das Startquadrat 13 Schritte vom Ziel entfernt. Hier ist ein Bild, das die Verbindungen zwischen möglichen Aufenthaltsorten der Figur, dem Start, dem Ziel, und der kürzesten Distanz jedes Ortes vom Ziel zeigt:
Ein Graph der dem Labyrinth entspricht
Es gibt ein Quadrat, das direkt südlich vom Start liegt (Zeile vier, Spalte drei), und das nur 12 Schritte vom Ziel entfernt ist. Daher ist die erste Bewegung "nach Süden". Südlich von diesem Quadrat ist eine 11. Wieder nach Süden. Wieder südlich ist eine 10. Dann nach Osten zu einer 9. Noch zwei Mal nach Osten zu einer 7, dann fünf Mal nach Norden zu einer 2. Ende damit, indem du ein Mal nach Westen gehst, zu einer 1, und dann noch einmal nach Norden, zum Ziel.
Wir werden jetzt nicht im Detail erklären, wie dieser Labyrinth-Suchalgorithmus funktioniert, aber vielleicht macht es dir ja Spaß, darüber nachzudenken, wie du das Labyrinth und die Figur mit JavaScript darstellen und den Algorithmus implementieren würdest.

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.