Backtracking (Labyrinth 3 )

 

Jetzt statten wir auch dich mit Kreide und Faden aus.

Führe den Helden aus dem Labyrinth.

ohne Kreide 

In unserer Darstellung wickelt der Held den Faden wieder auf, wenn er zurück geht.
Wenn er das nicht tut, kann er auf die Kreide verzichten, denn besuchte Felder erkennt er dann daran, dass dort der Faden liegt.
Das ist genau der originale Vorschlag Ariadnes aus der Sage.

 

Zum Abschluss dieses Abschnitts formulieren wir unser Vorgehen noch als Algorithmus.

 

Algorithmus 'Zum Ausgang'

solange nicht am Ausgang
      falls es ein angrenzendes, nicht markiertes Feld gibt
            bewege den Helden auf dieses Feld und markiere es
      sonst
            bewege den Helden zurück auf das zuletzt begangene Feld

Backtracking 

Dieser Algorithmus ist ein erstes Beispiel für die Backtracking-Strategie. Im nächsten Abschnitt werden wir dieses Prinzip allgemein beschreiben.

Beantworte zuvor noch folgende Frage.

Wie oft wird jetzt jedes Feld maximal begangen?  

Seite 3/10