Wie funktioniert der Algorithmus von Trémaux?
Neulich habe ich eine Folge Simpsons gesehen in der Lisa aus einem Labyrinth herausfand indem sie den Algorithmus von Trémaux anwendete. Ich würde gerne wissen wie dieser Algorithmus funktioniert.
2 Antworten
http://en.wikipedia.org/wiki/Mazesolvingalgorithm#Tremaux.27s_algorithm
Ist auf Englisch. In aller Kürze auf Deutsch: Du brauchst jede Menge Kreide. Wenn du losgehst, nachdem du i-wo im Labyrinth ausgesetzt wurdest, machst du einen Strich, wo du lang gehst. An einer Abzweigung entscheidest du dich für einen Weg, aber du markierst sowohl die Richtung, aus der du kommst, als auch den Weg, in den du abzweigst. Wenn du an einer bereits markierten Abzweigung ankommst, nimm möglichst einen noch nicht markierten Weg. Wenn das nicht möglich ist, nimm einen markierten Weg, markiere ihn nochmal (du kannst den Weg nehmen, den du gekommen bist). Nimm nie einen doppelt markierten Weg, denn du brauchst keinen Weg mehr als zweimal zu gehen. Wenn du keinen Ausgang findest, bringt dich diese Methode auf jeden Fall an den Ausgangspunkt zurück. Dann kannst du es in der anderen Richtung weiter versuchen.
Es handelt sich bei dem Algorithmus von Trémaux um eine effektive Implementierung einer Suche mit einer Suchtiefe erster Stufe.
http://www.youtube.com/watch?v=6OzpKm4te-E
Man kann natürlich auch einfach immer an der rechten oder immer an der linken Wand entlang gehen und kommt damit auch auf jedenfall ans Ziel. Das ist einfacher und man braucht keine Kreide. :-)
Nicht wirklich. Die rechte Handregel funktioniert nur zuverlässig wenn man schon am Eingang damit anfängt. Fängt man mittendrin damit an, kann man auch ständig eine von vielen große verwinkelten Säulen erwischen und läuft immer im Kreis.
Und genau die Ausgangssituation hatte auch Lisa in der Simpsonsfolge, da sie schon mittem im Labyrinth waren ;-) Insofern war die Tremaux-Methode schon deutlich sinnvoller. Zumal es ein Maisfeld war, und sie Striche in den Boden ziehen konnten, ganz ohne Kreide ;D LG