Backtracking (Labyrinth 2 )

	Der wahre Held braucht ein gute Systematik, die wir jetzt entwickeln. Dazu statten wir den Helden erst einmal mit Kreide aus. Damit malt er jedes begangene Feld im Labyrinth an.
	Wird es jetzt einfacher, den Helden aus dem Labyrinth zu führen?
klar	Mit den Markierungen weiß man, wo man überall schon war. Um zu vermeiden, dass man im Kreis geht, versucht man immer, auf noch nicht markierte Felder zu gehen.
Problem	Es kann vorkommen, dass man gar keine Wahl hat und ein markiertes Feld nochmals begehen muss. (Sollte dies bei dir nicht der Fall gewesen sein, so hast du sehr großes Glück gehabt. Wiederhole das Experiment mit einem anderen Labyrinth.)
	Das bisherige Vorgehen können wir algorithmisch so beschreiben:
	Algorithmus 'Im Labyrinth' 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 auf ein angrenzendes, markiertes Feld
nochmals klar	Wenn man nur noch markierte Felder um sich hat, ist man auf dem Holzweg. Man will umkehren. Das ist im obigen Algorithmus allerdings so noch nicht präzisiert. Man möchte also bis zur nächsten Kreuzung zurückgehen. Wenn dort auch schon alle Felder markiert sind, möchte man noch weiter zurück usw. Um 'zurück' zu gehen, muss man immer wissen, wo man her kam.
der Faden	In der griechischen  Sage hat eine kluge Frau (Ariadne) einem wahren Helden (Theseus) erklärt, wie das geht: Man spult einfach einen Faden, den Ariadne-Faden ab. Theseus im Labyrinth, J. W. Waterhouse (1862)
	Hier kannst du den Helden beobachten, wie er mit Kreide und Faden ganz systematisch aus dem Labyrinth findet. (Der Ariadne-Faden ist durch die blauen Punkte dargestellt).
genau beobachtet?	Im obigen Experiment arbeitet der Held die Möglichkeiten immer nach denselben Präferenzen ab. Ziehe jede Richtung auf das passende graue Feld.

Seite 2/10