Der Algorithmus von TREMAUX ist eine Methode, die man zum Beispiel in einem Labyrinth
verwendet, wenn man den Ausgang nicht so ohne weiteres finden kann. Sie führt uns
durch die Gänge, ohne einen zu vergessen. Und falls wir den Ausgang übersehen, so
kehren wir zum Schluss zu unserem Anfangsknoten zurück, nachdem wir durch jeden
Gang genau zweimal gelaufen sind.
Diese Methode wird auch bei den Straßenkehrmaschinen verwendet: Jede Straße wird
zweimal entlanggefahren, um beide Straßenseiten zu reinigen, und der besseren
Anschaulichkeit wegen gebe ich die Methode auch in der "Sprache einer Straßenkehrmaschine"
an :
- Start an einer beliebigen Kreuzung (Knoten) in beliebiger Richtung.
- Am Ende einer Sackgasse wird umgekehrt.
- Am Beginn und am Ende einer gereinigten Straßenseite wird ein Zeichen (Markierung) angebracht.
- An einem noch nie befahrenen Knoten wird durch eine beliebige andere Straße weitergefahren.
- Gelangen wir durch eine erst einseitig gereinigte Straße an einen schon einmal befahrenen Knoten, so
kehren wir um und reinigen die andere Straßenseite. War die andere schon sauber, dann suchen wir zur
Weiterfahrt eine noch gar nicht gereinigte Straße. Haben wir auch diese Möglichkeit nicht, so fahren wir in
einer beliebigen erst halbseitig gereinigten Straße weiter.
- Haben wir den Ausgang gefunden, so wird die Suche beendet.
Versuchen wir es doch einmal! Vorgegeben ist das zweite Labyrinth aus der Seite
"Der Faden der Ariadne". Dieses konnte man nicht
über die "Rechte - Hand - Regel" vom Knoten A aus verlassen. Wir wollen
einmal probieren ob man es mit dem Algorithmus von TREMAUX verlassen kann.
Startpunkt ist wieder der Knoten A.
In dieser Abbildung, habe ich meine Version der Lösung dargestellt es gibt natürlich
noch sehr viele andere. Der Weg des Algorithmus von TREMAUX ist farbig
gekennzeichnet, zum besseren Verständnis wurden an die Kanten Zahlen (1, 2, 3...)
heran geschrieben um die Reihenfolge festzulegen. Unser Weg führt durch die Knoten
A, B, C, D, E, F, G, B, G, K, F und L.
Meine Lösungsmöglichkeit ist ganz an die Eigenschaften von einer Straßenkehrmaschine
angepasst. Man kann die oben aufgezählten Bedingungen genau nachweisen.
- Mein Weg beginnt an dem Knoten A und fährt in die Richtung des Knoten B.
- Am Ende der Sackgasse, Knoten E , bin ich umgekehrt.
- Ich habe die Wege (Kanten), die ich zurückgelegt habe, farbig gekennzeichnet.
- Als ich am Knoten F ankam, dieser wurde vorher noch nicht von mir überquert, entschied ich mich in Richtung
Knoten G weiterzulaufen.
- Als ich den Knoten B erreichte bemerkte ich, dass ich diesen Knoten schon einmal erreicht hatte.
Ich entschloss mich, weil Kante 8 erst einmal zurückgelegt wurde, zum Knoten B zurückzugehen.
- Indem ich Knoten L erreichte, fand ich auch den Ausgang und meine Suche war damit beendet.
Doch jetzt wollen wir einmal probieren, ob wir auch eine schwerere Aufgabe lösen
können. Wir wollen eine Fahrtroute der Straßenkehrmaschine in einem richtigen
Stadtplan finden. In der vorliegenden Abbildung sind aber keinerlei Straßennamen
oder Plätze beschriftet, denn ich denke, dass würde nur zu Verwirrungen führen.
Die gelben Linien Stellen die Straßen dar und die grünen Flächen sind Häuser oder
Plätze. Am Punkt A beginnt die Fahrt meiner Straßenkehrmaschine. Sie fährt zuerst
die rosafarbene Tour ab in Richtung Nord - West. Dann auf der türkisfarbenen weiter
nach Osten. Sie schlägt eine Kehrtwendung ein, um auf einer rosa Linie zurückzufahren.
Später fährt sie auf der türkisen Linie weiter, diese wechselt dann wieder in rosa und
am Ende in türkis um. Dann verändert sie sich in eine orange Linie, als diese den
Knotenpunkt B erreicht, macht sie eine 180° Wendung und schließt an die
türkise Linie an. Diese wechselt wieder in rosa, dann türkis, später wieder in
rosa und fast am Ende noch einmal in türkis um. Als diese dann wieder zu rosa wurde,
und sich in Richtung Westen bewegte, gelange sie an den Knoten C dort schlug sie eine
180° Kurve und bewegte sich zum Ausgangspunkt A. Damit haben wir eine komplette
Fahrtroute abgeschlossen.
Die vielen Farben führen zwar auf dem ersten Blick zu Verwirrungen, aber ich glaube
wenn man sich intensiver damit beschäftigt hat ist es eigentlich leicht zu verstehen.
Nur eines muss vollkommen klar sein alle Linien, egal ob rosa, türkis oder orange,
gehören zu einem Fahrzeug. Und die ganzen Linien zusammen ergeben eine Route. Ich
habe die unterschiedlichen Farben nur benutzt, damit ihr die Route genau nachvollziehen
könnt.
Der Faden der Ariadne