Wege aus dem Labyrinth
3.5 Noch ein Stück Rekursion und mehr
Am Anfang war zu lesen:
In diesem Tutorial soll in die grundlegende Algorithmik eines „Versuch und Irrtum“-Verfahrens eingeführt werden. Wer es englisch will, bitte: Da heißt es trial and error. In der Informatik spricht man von Backtracking-Verfahren. Es wird sich zeigen, dass dieses Verfahren einen Zugang zu einer ganz neuen Klasse von Problemen liefert. Dabei spielt wiederum die Rekursion eine große Rolle.
Das gilt es jetzt zu beschreiben.
Um diese Beschreibung nicht zu unkonkret werden zu lassen, liegt diesem Tutorial am Ende eine Datei TtBilder.hlp bei. Auf diese Datei beziehe ich mich in den folgenden Zeilen.
Wir entwickeln nun eine Prozedur Wegsuche (zl, sp: Integer), die ausgehend von einem beliebigen, aber zulässigen Startpunkt (zl, sp) ? hier automatisch festgestellt von der Prozedur Startplatz ? den Weg zu den Ausgängen des Labyrinths findet und markiert.
Zu Bild „Erste Schritte“:
Ausgehend von dem blau umrandeten Startpunkt sind hier vier Streckenabschnitte unseres Weges beschrieben.
Zuerst wird im Startpunkt eine Marke gesetzt und dann „Laufe nach rechts“ aufgerufen, was keine Aktion bewirkt (Merksatz 2 – Zur festgelegten Reihenfolge siehe Merksatz 1.). Jetzt wird „Laufe nach unten“ versucht, und hier kann ebenfalls nichts erreicht werden. Erst „Laufe nach links“ kommt zu einem Ergebnis. Und das geht so bis zur ersten roten Umrandung. Nun kommt „Laufe nach rechts“ auch nicht zum Ziel. Erst „Laufe nach unten“ findet ein Wegelement vor. Und damit weiter bis zur nächsten roten Umrandung.
Halt! Hier muss erst noch eine Frage erlaubt sein: Warum wird das (grün markierte) Tor auf dem zweiten Streckenabschnitt nicht angesteuert?
Der rotbraune Pfeil zeigt die Richtung an, in der das Programm abgearbeitet wird. Und wenn wir Merksatz 1 zu Rate ziehen, ist das Ergebnis klar: Nach unten geht VOR nach links.
Die Abschnitte 3 und 4 auf unserer „Reise“ bedürfen keiner weiteren Erklärung.
Zu Bild „Wie sieht der nächste Schritt aus (1)?“:
Das Programm ist inzwischen auf dem nächsten Wegeabschnitt unterwegs gewesen. Jetzt steht es an der Wegkreuzung und weiß nicht weiter.
Weißt Du, wie es weitergeht?
Doch ganz einfach, wenn Du wieder Merksatz 1 ansiehst.
Zu Bild „Wie sieht der nächste Schritt aus (2)?“:
Die rote Umrandung in diesem Bild zeigt uns die nächste Wegkreuzung an. Jetzt weißt Du natürlich längst, wie es weitergeht!!
Zu Bild „Am Tor angekommen“:
Das Programm hat zum ersten Mal ein Tor erreicht. Jetzt wird der erste Teil der Prozedur, nämlich
if IsStein (zl,sp,leer) OR IsStein (zl,sp,tor) then
begin
if IsStein (zl,sp,tor) then Ausgang
wirksam. Die Prozedur Ausgang wird aufgerufen und hält den Programmlauf an, bis durch einen Tastendruck die „Fahrt“ wieder freigegeben wird.
Zu Bild „Sackgasse“:
Jetzt wird es kriminell! Soeben ist die Suche nach Wegen in einer Sackgasse gelandet. Kein Weg führt nach vorn, und kein Weg führt wieder zurück! Aussichtslos!
Sämtliche Versuche auf der Rekursionsstufe am Ende der Sackgasse schlagen fehl. Entsprechend dem (auch in der Datei vorhandenen) Struktogramm wird nach dem Ausprobieren aller Richtungen die Markierung entfernt. Damit ist die Rekursionsstufe vollständig abgearbeitet. Es werden nun die nicht versuchten Richtungen auf der vorletzten Rekursionsstufe aufgerufen. Da alle Versuche fehlschlagen, wird die Markierung wieder entfernt und die davorliegende Rekursionsstufe weiter bearbeitet. ? Auch alle weiteren Versuche auf den außerdem entstandenen Rekursionsstufen schlagen fehl. Damit werden alle Markierungen bis zum Ende der roten Umrandung zurückgenommen.
Zum ersten Mal setzt hier das Backtracking ein.
Und hier noch einmal: Unter Backtracking versteht man das Zurücknehmen von nicht zum Ziel führenden Schritten bei einer Problemlösung nach der Methode von „Versuch und Irrtum“. Algorithmische Verfahren, die nach diesem Prinzip arbeiten, nennt man Backtracking-Verfahren.
Im Bild Sackgasse sind (blau gekennzeichnet) noch zwei weitere Sackgassen in diesem Labyrinth eingezeichnet, auf die die gleichen Bedingungen zutreffen wie eben beschrieben.
Zu Bild „Und noch ein Tor“:
Dieses Tor (blau markiert) wurde am Anfang aus den genannten Gründen nicht behandelt. Jetzt bei der Abarbeitung der einzelnen Rekursionsstufen wird auch dieses Tor markiert und angezeigt.
Wenn du dir jetzt das Struktogramm und die fünf Merksätze vornimmst, wirst du noch tiefer in das Geschehen innerhalb der Prozedur eindringen können.
Um dir die Einzelheiten noch einmal in Erinnerungen zu rufen, kannst du jetzt mit dem Programm Wege.dpr einige „Probeläufe“ absolvieren. Da wird dir sicher noch manches dabei klar werden.
Der Quelltext dieses Programms setzt sich aus folgenden Dateien zusammen:
- Wege.dpr,
- uWege.pas,
- IncDefin.inc und
- IncProcs.inc.
Da er ausführlich kommentiert ist, dürfte es für das Verständnis sicher keine Probleme geben.
So, damit ist der erste Themenkreis dieses Tutorials abgeschlossen. Solltest Du noch Fragen zur Rekursion haben, sieh dir – wie schon oben geschrieben – das Tutorial „Rekursive Algorithmen“ an. Danke.
2 Gedanken zu „Wege aus dem Labyrinth“
Kommentare sind geschlossen.
Hallo,
Die Datei „backtracking_src.zip“ lässt sich leider nicht herunterladen. Könnt ihr mir bitte helfen?
Hans
Ich habe die Datei verlinkt.
Vielen Dank für den Hinweis!