Wie kommt man von einer (komplexen) Problemstellung auf eine algorithmische Beschreibung einer (schlauen) Lösung?
Als Beispiel wollen wir einen Algorithmus finden, der uns aus einem Labyrinth rausbringt.
Labyrinth bezeichnet ein System von Linien oder Wegen, das durch zahlreiche Richtungsänderungen ein Verfolgen oder Abschreiten des Musters zu einem Rätsel macht.
Ausgang finden
Als Einstieg, versuchen wir den Ausgang aus diversen Labyrinthen zu finden. Wir leiten unsere Spielfigur an, indem wir Befehlsblöcke wie ein Puzzle zusammensetzen.
Dies machen wir an Hand des Blockly-Spiels «maze».
Aufgabe: Blockly
- Starte das Blockly-Spiel «Labyrinth» in deinem Browser
- Wie viele Levels schaffst du?
Verallgemeinerung
Für die Beispiel-Labyrinthe auf der Blockly-Webseite hast du hoffentlich eine Lösung gefunden. Aber ist das schon der gesuchte Algorithmus?
- Allgemeinheit
- Funktioniert deine Lösung mit jedem Labyrinth und jedem Startpunkt?
- Korrektheit
- Findet dein Algorithmus immer den Ausgang?
Aufgabe
Besprecht in Zweiergruppen mögliche Ansätze für eine allgemeine Lösung, also ein Vorgehen, womit man aus jedem Labyrinth herausfindet
Zusatzaufgabe
Falls ihr so eine allgemeine Lösung gefunden habt: könnt ihr diese im Blockly-Spiel «maze» umsetzen? Man müsste ja damit in jedem Level den Ausgang finden.
Lösung
Der «Linke-Hand»-Algorithmus:
- suche eine beliebige Wand und drehe dich so, dass deine linke Hand die Wand berührt
- gehe immer weiter an dieser Wand entlang, so dass die linke Hand nie den Kontakt verliert
- wenn du den Ausgang erreicht hast, kannst du die Wand loslassen
Hinweis: Natürlich funktioniert das auch, wenn man statt der linken die rechte Hand benutzt – aber man muss sich entscheiden und dann dabei bleiben.
Noch ein Hinweis: So einfach lässt sich das formulieren, weil man nicht mehr zwischen verschiedenen Richtungen unterscheiden muss, wenn man einfach einer Wand folgt – die richtigen Drehungen passieren automatisch, selbst am Ende einer Sackgasse.
Korrektheit
Es scheint einleuchtend, dass die Linke-Hand-Regel in jedem Labyrinth, von jedem Startpunkt aus, immer in endlicher Zeit zum Ausgang führt.
Aber können wir sicher sein?
Hier hilft ein in der Informatik üblicher Trick: man repräsentiert das Problem in einer anderen Form, in der alle für die Lösung irrelevanten Details weggelassen werden.
Abstraktion
Ist der Prozess der Vereinfachung und des Weglassens der nicht-relevanten Dinge.
Wir wollen also wissen, ob die Linke-Hand-Regel in jedem Labyrinth den Ausgang findet!
Welche Elemente des Labyrinths sind für unser Problem relevant?
Folgende Elemente interessieren uns nicht:
- In den Sackgassen drehen wir um
- In den Kurven folgen wir dem Weg
- Die Länge der Gänge spielt auch keine Rolle
Was uns interessiert sind:
- Start- und Endpunkt
- Kreuzungen
- deren Reihenfolge
Wir markieren also mal alle Kreuzungen und nummerieren diese:
Nun können wir den Startpunkt und die Kreuzungen anders darstellen, nämlich als ein sogenannter Baum. Dabei werden Kreuzungen als sogenannte Knoten dargestellt und Gänge zwischen den Kreuzungen als Verbindung zwischen den Knoten, den sogenannten Kanten:
Wir schauen uns an, in welcher Reihenfolge die Kreuzungen besucht werden:
Diesen Pfad tragen wir nun im Baum ein: Wir erkennen nun, dass systematisch alle Kreuzung abgearbeitet werden. Gibt es keine Kreuzung mehr, so geht man zur letzten Kreuzung zurück (Backtracking) und nimmt dort einen anderen Weg – bis man das Ziel findet.
Linke-Hand-Algorithmus
Wir haben also unseren Algorithmus gefunden: Wir gehen geradeaus bis wir eine Mauer finden, dann berühren wir mit der linken Hand die Mauer und folgen ihr ohne loszulassen bis wir den Ausgang erreichen.