Hauptinhalt
Informationstechnik
Kurs: Informationstechnik > Lerneinheit 1
Lektion 1: Einführung in AlgorithmenRoutensuche
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.
Für Pac-Man brauchen wir eine Karte des Labyrinths. Diese Karte zeigt Verbindungen zwischen benachbarten offenen Quadraten in dem Labyrinth—oder ein Mangel an Verbindungen, wenn es eine Mauer dazwischen gibt—und die Aufgabe ist einen Weg entlang schwarzer Quadrate zu finden, der den Geist zu Pac-Man führt.
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.
Ein Labyrinth erkunden
Labyrinthspiele machen Spaß, also lass uns tiefer in eines eintauchen. In unserem Spiel kann die Hauptfigur zu Zielen in einem Labyrinth navigieren.
Als menschlicher Spieler steuerst du die Hauptfigur, indem du auf das nächste Ziel im Labyrinth klickst, und der Computer findet heraus, wie er die Figur dorthin bewegen kann. Das Ziel ist mit einem roten Rechteck mit der Aufschrift "GOAL" markiert, und die Figur startet auf ihrem ersten Ziel, dem Startfeld. Versuche es unten zu spielen:
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 das 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.
Hier ist die Idee hinter dem Algorithmus, die dieses Programm benutzt: bewege 1 Quadrat näher ans Ziels—die Stelle, die der Benutzer anklickt—bei jedem Schritt. 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:
- Beginne am Zielquadrat. Wie weit ist das Ziel vom Ziel entfert? Null Schritte, also markiere das Ziel mit der Zahl 0.
- 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.
- 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.
- 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.
- Markiere weiter Quadrate im Labyrinth nach dem zunehmenden Abstand vom Ziel. Nachdem die Quadrate mit der Zahl
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:
Es gibt ein Quadrat, das direkt südlich vom Start liegt, 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 8. 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.
Willst du an der Diskussion teilnehmen?
Sälllüüüüüüü?(1 Bewertung)
kann mann wenn man den text liest ep gewinnen(0 Bewertungen)- gibt es das auch nur mit bildern?(0 Bewertungen)
gibt es größere zahlen als unendlich(0 Bewertungen)