Kapitel 3-3

Jedes Kind hat schon Labyrinthe kennengelernt.
Nicht nur die Aufgabenstellung, sondern auch Lösungsverfahren lassen sich einfach geometrisch veranschaulichen. Hier sei auch an den Aiadne-Faden erinnert, der die Vergegenständlichung des Backtrackings im Labyrinth ist.
Die Aufgabe ist leicht und plausibel abwandelbar:

        Suche einen Weg zu einem Ausgang
        Suche einen Weg zu jedem Ausgang
        Suche alle Wege zu einem Ausgang
        Suche alle Wege zu allen Ausgängen
        Suche den kürzesten Weg zu einem Ausgang
        und mehr

Man kann den Schülern Labyrinthe auf dem Papier vorgeben, bis sie sich ihres Vorgehens bewußt sind und einen Algorithmus beschreiben können. Es gibt auch einige Computerspiele (z.B. MastMaze), in denen sich die Schüler durch Labyrinthe bewegen müssen. Gegenüber Papierlabyrinthen haben sie hier nicht den Vorteil der Vogelperspektive, was für die spätere Algorithmusentwicklung vorteilhaft ist.
Eine Möglichkeit der Modellierung ist das Programm "Nikki, der Roboter". Es hilft den Schülern, den Begriff der Umwelt im Computer besser zu erfassen und ihren Lösungsweg in einen Algorithmus zu fassen.
Enthält der vom Schüler benutzte Algorithmus einen Fehler, läßt sich leicht durch Änderung des Labyrinths ein geeigneter Test konstruieren.
Vorteilhaft für eine zeitige Behandlung ist die Möglichkeit, die Ausgabe als Pseudografik zu gestalten. Zu empfehlen ist die farbige Gestaltung, um Mauern, bereits erkundete Wege, "Faden" und aktuelle Position deutlich zu markieren.
Es gibt keine feste Rekursionstiefe. Das hat den Vorteil, dass die Schüler Backtracking nicht einfach nur als systematisches Probieren begreifen und nicht der Versuchung erliegen können, verschachtelte FOR-TO-Schleifen zu programmieren.
Als Vorstufe des Backtrackings ist auch "Trial And Error" denkbar

Anfang

vor

zurück

3.3.2 Probleme

Die Initialisierung kann einen erheblichen Aufwand darstellen.
Die Rekursionstiefe kann erheblich werden und schnell vom System gesetzte Grenzen sprengen.

Beide Probleme ließen sich entschärfen, wenn man noch auf dem Papier aus dem Labyrinth einen Graphen entwickelt und diesen eingibt (zum passenden Algorithmus). Dann muss man aber auf die Veranschaulichung am Monitor verzichten. Deshalb empfehlen wir diese Lösung nicht. Es wird wohl sinnvoll sein, mit kleinen Figuren zu beginnen und beim Übergang zu größeren Labyrinthen den Algorithmus anzupassen. So wird auch die Komplexität des Problems allmählich gesteigert.

Anfang

vor

zurück

3.3.3 Einordnung in den Unterricht

3.3.3.1 Voraussetzungen

Wie in 3.3.1 beschrieben, ist das Labyrinth-Problem in seinem Kern gut für einen zeitigen Einsatz geeignet, also als erstes Programm mit Backtracking-Prinzip. Die rekursive Programmierung sollte allerdings vorher eingeführt worden sein, um keine Gleichheit zu assoziieren.
Weitere notwendige Voraussetzungen sind das zweidimensionale Array und das Einlesen von Dateien. Um die Gesamtaufgabe nicht unnötig komplex zu gestalten, ist es aber denkbar, die Initialisierungsprozedur bereitzustellen.

program labyrint;
{ Hartmut Scheffer, Erweiterungsstudium Uni Potsdam, E 15221 }
uses crt;

const LABFILE = 'test.lby';
MAXLAENGE = 40;
MAXBREITE = 25;

type TLabElement = (Mauer,
                    Weg,        { unbekannter Weg }
                    Gang,       { erkundeter Weg }
                    Pfad,       { "Faden" }
                    Start,
                    Ausgang);

var Laby   : array[1..MAXLAENGE, 1..MAXBREITE] of TLabElement;
    XLaenge,
    YBreite,
    XLinks,
    YOben,
    XStart,
    YStart : shortint;

procedure Schreibe(x, y : shortint);
   begin
    gotoxy(XLinks + 2 * X - 2, YOben + Y - 1);
    case laby[X,Y] of
        Mauer   : textcolor(7);
        Weg     : textcolor(1);
        Gang    : textcolor(15);
        Pfad    : textcolor(14);
        Start   : textcolor(9);
        Ausgang : textcolor(1);
        end;
   write(chr(219),chr(219));                 { 2 Zeichen breite Darstellung }
   end;

function Labyrinth: boolean;                 { Initialisierung }
   var yL, xL : shortint;
       Zeile : string;
       f      : text;
   begin
   assign(f, LABFILE);
   reset(f);
   read(f, Laenge);
   readln(f, Zeile);
   read(f, Breite);
   readln(f, Zeile);
    if (XLaenge > MAXLAENGE) or (YBreite > MAXBREITE)
        then begin
            writeln('Das Labyrinth ist zu groß');
            Labyrinth := false;
            end
        else begin
            for YL := 1 to MAXBREITE do
                for XL := 1 to MAXLAENGE do
                    Laby[XL,YL] := Mauer;
            XLinks := (40 - XLaenge);          { 2 Zeichen breite Darstellung }
            YOben := (25 - YBreite) div 2;
            XStart := 0;
            YStart := 0;
            for YL := 1 to YBreite do
                begin
                readln(f, Zeile);
                for XL := 1 to XLaenge do
                    begin
                    case Zeile[XL] of
                        'W' : Laby[XL,YL] := Weg;
                        'A' : Laby[XL,YL] := Ausgang;
                        'S' : begin
                              Laby[XL,YL] := Start;
                              XStart := XL;
                              YStart := YL;
                              end;
                        end;
                    Schreibe(XL,YL);
                    end;
                end;
            Labyrinth := true;
            end;
   Close(f);
   end;

procedure SucheAusgang;
begin
{ Hier ist der Backtracking-Algorithmus zu entwickeln }
writeln;
writeln('Algorithmus fehlt noch');
end;

{Main}
begin
clrscr;
if Labyrinth then SucheAusgang;
readln;
end.

Das Hauptprogramm laesst sich auch einfacher gestalten:

begin
clrscr;
Labyrinth; { Prozedur! }
SucheAusgang;
readln;
end.

Listing: lab_init.pas

Anfang

vor

zurück

3.3.3.2 Nachnutzung

Die Eignung als Prüfungsthema soll hier nicht untersucht werden. Es sei lediglich darauf hingewiesen, dass die vielfältige Abwandelbarkeit Möglichkeiten eröffnet.
Mit der Einführung von Schleifen in das Labyrinth läßt sich das Thema Optimierungsstrategien behandeln.
Die Ablösung der Pseudografik durch echte Grafik eröffnet ein weites Feld.
Das Thema ist auch geeignet, um bei der Einführung neuer Strukturen deren Vorteile darzustellen, z.B.:

records
Maushandling (bei der Initialisierung)
Zeigervariable (Wegbeschreibung)
objektorientierte Programmierung

Anfang

vor

zurück

3.3.4 Stellen der Aufgabe

Wir gehen von einem Labyrinth aus, bei dem Wege und Mauern gleich dick sind. Der Ausgangspunkt liegt im Innern des Labyrinths, die Ziele am Rand. Es ist zu prüfen, ob es einen Weg nach draußen gibt. Wenn es einen gibt, ist er zu beschreiben.
Wird die Aufgabe zur Einführung des Backtrackings verwendet, läßt sich das Prinzip erklären, indem die Bildschirmausgabe des fertigen Programms mit einem geeigneten Labyrinth gezeigt wird.

Für den Anfang empfiehlt sich ein Labyrinth ohne Schleifen, so dass der Weg nicht protokolliert werden muss. Auch die Ausgänge kann man anfangs verbauen, so dass man sie

Nach der Lösung dieses Grundmodells kann man die Aufgabe komplizierter gestalten.

Anfang

vor

zurück

3.3.5 Analyse und Lösung

3.3.5.1 Die Programmstruktur

Neben dem Ariadne-Faden gibt es noch andere Möglichkeiten der gegenständlichen Beschreibung der Aufgabe, zum Beispiel folgende:

Ein Roboter wird losgeschickt, das Labyrinth zu erkunden und nach Rückkehr den Weg zu beschreiben. Der Roboter entspricht dann der zu entwickelnden Prozedur. Man kann die Aufgabe in zwei Bestandteile zerlegen:

Der Lehrer kann empfehlen, dass zunächst nur die Erkundung programmiert wird. Damit konzentriert man die Aufmerksamkeit auf das Backtracking. Als Rückmeldung genügt zunächst die Bildschirmdarstellung (Delay einsetzen).
Zur Anzeige enthält die Typdeklaration TLabElement neben den Bezeichnern Mauer, Start, Ausgang und Weg noch Gang (erkundeter Weg) und Pfad (Ariadne-Faden). Zur Entwicklung des Algorithmus wählt man einen kleinen Ausschnitt.

Bei der Analyse der Erkundung sollte man herausarbeiten, dass der "Roboter" nur die unmittelbare Umgebung erkunden kann und demzufolge auf jedem neu betretenen Feld die gleiche Erkundung ausführen muss. Es ist möglich, dass Schüler eine Repeat-Schleife vorschlagen, welche dann auf jedem Feld durchlaufen wird. Man kann einwenden, dass dann eine Speicherung des Weges erforderlich ist. Gewichtiger ist wohl als Argument, dass durch die vielen Verzweigungen schnell der Überblick verloren geht.
Um den Gedanken zur Rekursion zu lenken, sollte man das Bild vom Faden aufgreifen oder das Bild vom Roboter dahingehend weiterentwickeln, dass man erklärt, dass der Roboter sich seine Position sehr einfach merken kann, indem er seinen Platz nicht verläßt. Das Erkunden der nächsten Position überträgt er einfach einem neuen Roboter, damit hat man einen rekursiven Aufruf.

Anfang

vor

zurück

3.3.5.2 Möglichkeiten der Reihenfolge der Erkundung des Labyrinths

Ich kann mir 3 Varianten vorstellen:

A Immer an der Wand entlang

Das ist für Menschen im Labyrinth am einfachsten, insofern ist damit zu rechnen, dass ein entsprechender Vorschlag kommt. Auch wenn Variante B einfacher zu programmieren ist, kann man auch diese Variante programmieren lassen. Praktisch bedeutet das, dass an jeder Verzweigung zunächst der (z.B.) linke und zuletzt der rechte Zweig erkundet wird.

B Windrose

Immer mit der gleichen Richtung zu beginnen, ist am einfachsten zu programmieren. Die Richtungen kann man (z.B.) mit Nord, Ost, Süd, West bezeichnen.

C Trial and error

Das ist kein Backtracking und soll hier nicht weiter betrachtet werden.

Anfang

vor

zurück

3.3.5.3 Der rekursive Algorithmus

Die Erkundung muss folgendes leisten:
Variante A (aus 3.3.5.2):

Variante B:

gleichwertig ist:

Die "magere" Variante A hat dann aber immer noch ein Problem bei Schleifen im Labyrinth, deshalb ist auch bei "Immer an der Wand lang" Variante B zu empfehlen. Auf "Pfad" kann man verzichten, es dient lediglich der Visualisierung.

Anfang

vor

zurück

3.3.5.4 Besonderheiten des Startfeldes

Das Startfeld behält in der Ausgabe seine Farbe, hier darf also die Prozedur 'Schreibe' nicht ausgeführt werden. Vor allem muss aber vom Startfeld in alle 4 Richtungen erkundet werden. Deshalb erhält das Startfeld eine eigene Prozedur 'SucheAusgang', aus der dann die Rekursion 'Erkunde' gestartet wird.
Hier könnte man auch noch den Fall behandeln, dass das Startfeld am Rand liegt.

Anfang

vor

zurück

3.3.5.5 Variablen, Parameterübergabe

Natürlich benötigt die Prozedur die Koordinaten x,y des zu erkundenden Feldes als Rekursionsparameter. Bei Variante A muss darüber hinaus erkennbar sein, aus welcher Richtung man zu diesem Punkt gelangt ist. Diese kann man in Form eines zweiten Koordinatenpaares übergeben.

Anfang

vor

zurück

3.3.5.6 Drei zu erkundende Felder - Schleife oder Einzelaufruf?

Schüler, die vom Mathematik-Profilkurs das Thema "Drehung in Polarkoordinaten" kennen, wissen vielleicht, dass hier eine Schleife möglich ist. Andere werden sich eher fragen, wozu bei lediglich 3 bis 4 Durchläufen eine Schleife nützlich ist.
Argumente für die Schleife:

"Immer an der Wand entlang" ist mit Schleife wesentlich einfacher, unterscheidet sich von "Windrose" nur durch die Initialisierung.
Heißt die Aufgabe "Finde einen Weg", so muss die Suche abgebrochen werden, was mit Schleife einfacher ist.
Wird das Labyrinth zu groß, sollte aus obengenannten Gründen nur an jedem Knoten eine neue Rekursion gestartet werden. Das wird sich mit Schleife einfacher machen lassen.

Anfang

vor

zurück

3.3.5.7 Die Schleife

Die
procedure Erkunde(X, Y, NebenX, NebenY : shortint);
hat die Aufgabe, die Umgebung des Feldes (X,Y) zu erkunden, wobei der Aufruf aus (NebenX, NebenY) erfolgte. Mit
var Temp, i : shortint;
stehen 2 Variable bereit. i ist eine Zählvariable, die Variable Temp wird zur Berechnung benötigt.
Initialisierung:
In Variante A ist keine Initialisierung erforderlich, da die Werte übergeben werden. Dies ist auch der Grund dafür, dass in allen nachfolgenden Beispielen erst zum nächsten Feld gewechselt wird und dieses dann erkundet wird.
Variante B: West
    NebenX := X - 1;
    NebenY := Y;
Schleifentyp: For-To, Var. A: 3, Var. B: 4 Schleifendurchläufe
Berechnung von NebenX, NebenY:
Wie aus der Tabelle erkennbar ist,

lassen sich NebenX und NebenY berechnen, nachdem der alte Wert von NebenX in
    Temp := NebenX;
festgehalten wurde:
    NebenX := NebenX - (NebenX - X) - (NebenY - Y);
    NebenY := NebenY + ( Temp - X) - (NebenY - Y);
Jedes Nebenfeld ist dann zu erkunden.
    Erkunde(NebenX,NebenY,X,Y);
Ergänzt wird die Prozedur durch einige Befehle zu Darstellungs- und Testzwecken, die natürlich auch entfallen können. WINDROSE, TEST und WARTE sind Konstanten, MeldeGefunden(X,Y) eine nach eigenem Gutdünken gestaltbare Prozedur.

Anfang

vor

zurück

3.3.5.8 Die gesamte Prozedur

Die gesamte Prozedur kann dann folgendermaßen aussehen:

procedure Erkunde(X, Y, NebenX, NebenY : shortint);
    var Temp, i : shortint;
    begin
    if WINDROSE then begin
        NebenX := X - 1;
        NebenY := Y;
        end;
    case laby[X, Y] of
        Ausgang : MeldeGefunden(X,Y);
        Weg     : begin
                  laby[X, Y] := Pfad;
                  Schreibe(X, Y);
                  if TEST then delay(WARTE);
                  for i := 1 to 4 do
                      begin
                      Temp := NebenX;
                      NebenX := NebenX - (NebenX - X) - (NebenY - Y);
                      NebenY := NebenY + ( Temp - X) - (NebenY - Y);
                      Erkunde(NebenX,NebenY,X,Y);
                      end;
                  if TEST then delay(WARTE);
                  laby[X, Y] := Gang;
                  Schreibe(X, Y);
                  end;
        end;
    end;

Wie in 3.3.5.3 erwähnt, ist die folgende Prozedur gleichwertig:

procedure Erkunde(X, Y, AltX, AltY : shortint);
    var NeuX, NeuY, Temp, i : shortint;
    begin
    laby[X, Y] := Pfad;
    Schreibe(X, Y);
    if WINDROSE
        then begin
            NeuX := X - 1;
            NeuY := Y;
            end
        else begin
            NeuX := AltX;
            NeuY := AltY;
            end;
    if TEST then delay(WARTE);
    for i := 1 to 4 do
        begin
        Temp := NeuX;
        NeuX := NeuX - (NeuX - X) - (NeuY - Y);
        NeuY := NeuY + (Temp - X) - (NeuY - Y);
        if laby[NeuX,NeuY] = Weg then Erkunde(NeuX,NeuY,X,Y);
        if laby[NeuX,NeuY] = Ausgang then MeldeGefunden(NeuX,NeuY);
        end;
    if TEST then delay(WARTE);
    laby[X, Y] := Gang;
    Schreibe(X, Y);
    end;

Diese Prozedur enthält außerdem zusätzliche Variablen und andere Bezeichner zwecks leichterer Verständlichkeit.

Anfang

vor

zurück

3.3.5.9 Die Startprozedur

Wie in 3.3.5.4 dargestellt, braucht das Startfeld eine eigene Prozedur (Dies kann auch das Hauptprogramm sein). Nach 'Erkunde' ergibt sich 'SucheAusgang' problemlos.

Anfang

vor

zurück

3.3.5.10 Das Programm

Das Programm sieht dann etwa folgendermaßen aus:

program labyrint;
{ Hartmut Scheffer, Erweiterungsstudium Uni Potsdam, E 15221 }
uses crt;

const TEST = true;
      WINDROSE = false;
      WARTE = 200;
      LABFILE = 'test2.lby';
      MAXLAENGE = 40;
      MAXBREITE = 25;

var Laby   : array[1..MAXLAENGE, 1..MAXBREITE] of TLabElement;
    XLaenge,
    YBreite,
    XLinks,
    YOben,
    XStart,
    YStart : shortint;

procedure Schreibe(X, Y : shortint);
    begin
    gotoxy(XLinks + 2 * X - 2, YOben + Y - 1);
    case laby[X,Y] of
         Mauer   : textcolor(8);
         Weg     : textcolor(1);
         Gang    : textcolor(15);
         Pfad    : textcolor(14);
         Start   : textcolor(9);
         Ausgang : textcolor(1);
         end;
    write(chr(219),chr(219));                 { 2 Zeichen breite Darstellung }
    end;

function Labyrinth: boolean;                 { Initialisierung }
    var YL, XL : shortint;
        Zeile : string;
        f      : text;
    begin
    assign(f, LABFILE);
    reset(f);
    read(f, XLaenge);
    readln(f, Zeile);
    read(f, YBreite);
    readln(f, Zeile);
    if (XLaenge > MAXLAENGE) or (YBreite > MAXBREITE)
        then begin
            writeln('Das Labyrinth ist zu gross');
            Labyrinth := false;
            end
        else begin
            for YL := 1 to MAXBREITE do
                for XL := 1 to MAXLAENGE do
                    Laby[XL,YL] := Mauer;
            XLinks := (40 - XLaenge);          { 2 Zeichen breite Darstellung }
            YOben := (25 - YBreite) div 2;
            XStart := 0;
            YStart := 0;
            for YL := 1 to YBreite do
                begin
                readln(f, Zeile);
                for XL := 1 to XLaenge do
                    begin
                    case Zeile[XL] of
                        'W' : Laby[XL,YL] := Weg;
                        'A' : Laby[XL,YL] := Ausgang;
                        'S' : begin
                              Laby[XL,YL] := Start;
                              XStart := XL;
                              YStart := YL;
                              end;
                        end;
                    Schreibe(XL,YL);
                    end;
                end;
            Labyrinth := true;
            end;
   Close(f);
   end;

procedure MeldeGefunden(X, Y: shortint);
    begin
    gotoxy(XLinks + 2 * X - 2, YOben + Y - 1);
    textcolor(7);
    write(chr(219),chr(219));                 { 2 Zeichen breite Darstellung }
    end;

procedure Erkunde(X, Y, AltX, AltY : shortint);
    var NeuX, NeuY, Temp, i : shortint;
    begin
    laby[X, Y] := Pfad;
    Schreibe(X, Y);
    if WINDROSE
        then begin
            NeuX := X - 1;
            NeuY := Y;
            end
        else begin
            NeuX := AltX;
            NeuY := AltY;
            end;
    if TEST then delay(WARTE);
    for i := 1 to 4 do
        begin
        Temp := NeuX;
        NeuX := NeuX - (NeuX - X) - (NeuY - Y);
        NeuY := NeuY + (Temp - X) - (NeuY - Y);
        if laby[NeuX,NeuY] = Weg then Erkunde(NeuX,NeuY,X,Y);
        if laby[NeuX,NeuY] = Ausgang then MeldeGefunden(NeuX,NeuY);
        end;
    if TEST then delay(WARTE);
    laby[X, Y] := Gang;
    Schreibe(X, Y);
    end;

procedure SucheAusgang;
    var X, Y, NeuX, NeuY, Temp, i : Shortint;
    begin
    X := XStart;
    Y := YStart;
    NeuX := X - 1;
    NeuY := Y;
    for i := 1 to 4 do
        begin
        Temp := NeuX;
        NeuX := NeuX - (NeuX - X) - (NeuY - Y);
        NeuY := NeuY + (Temp - X) - (NeuY - Y);
        if laby[NeuX,NeuY] = Weg then Erkunde(NeuX,NeuY,X,Y);
        end;
    end;

{Main}
begin
clrscr;
if Labyrinth then SucheAusgang;
readln;
end.

Listing: laby1.pas

Hinweis: Das Programm ist weitgehend ungesichert gegen fehlerhafte Labfiles.

Anfang

vor

zurück

3.3.6 Mögliche Weiterentwicklungen

Gleich im Anschluss an die Lösung der Grundaufgabe, im späteren Unterricht oder über den Unterrichtsstoff hinausgehend kann an der Aufgabe weitergearbeitet werden.

Die Lösung kann als Zeichenkette in einer Datei ausgegeben werden.
Durch gleiche Darstellung von Weg und Mauer lässt sich der Lösungsweg vor dem Nutzer verbergen. Das Programm kann dann interaktiv gestaltet werden.

Die in 3.3.1 genannten Varianten können gelöst werden. Bei der Behandlung des Themas Backtracking müssen diese Fragen mindestens genannt werden.
Im Zusammenhang mit dem Abbruch der Suche nach der Entdeckung des ersten Ausgangs kann man die for-to-Schleife durch eine repeat-Schleife ersetzen.
Bei der Suche nach dem kürzesten Weg kann man den Typ TLabElement durch ein Element Knoten ergänzen und so Schleifen vermeiden.

Die grafische Darstellung kann verbessert werden.
Die Frage nach effektiveren Algorithmen wird sich wohl nur außerhalb des Unterrichts beantworten lassen. Eventuell kann man diese Aufgabe Absolventen stellen, die ein Informatik-Studium aufnehmen.

Anfang

zurück

3.3.7 Labyrinthe

Hinweis: *.lby sind Textdateien


Listing: lby0.lby	Listing: lby1.lby


Listing: lby2.lby	Listing: lby3.lby


Listing: lby4.lby	Listing: lby5.lby

Benutzer: Gast • Besitzer: seminar • Zuletzt geändert am: