effizienter Algorithmus um alle Felder eines Irrgarten zu besuchen

[pointhi]

Hy,

Ich arbeite wie letztes jahr wieder daran, um beim RCJ teilzunehmen. Wie letztes Jahr auch in der Disziplin Rescue B.

Dieses Jahr wurden die Bedingungen verschärft, und der Roboter kann mit der Rechten-Hand-Regel nicht mehr das gesamte Labyrinth absuchen. Das Problem sind die "Freistehenden Wände". Ich hab mich mal ein wenig informiert und hätte ein paar fragen bezüglich der Algorithmen:

(http://de.wikipedia.org/wiki/L%C3%B6sungsalgorithmen_f%C3%BCr_Irrg%C3%A4rten)

Ich hab mal 2 Algorithmen gefunden die passen können:

* Trémaux-Algorithmus
* Algorithmus von Gaston Tarry

Ich hab jetzt den Trémaux-Algorithmus auf einem Blatt Papier gemacht und bin auf eine kleine ungereimtheit gestoßen. Die Frage ist jetzt ob dieser Algorithmus sicher alle Felder absucht, oder welche die innen liegen übersehen kann (hab nichts im internett dazu gefunden). Villeicht hab ich auch einen Denkfehler gemacht.

Leider hab ich auch nirgends eine Visualisierung gefunden, wo man eigene Labyrinthe eingeben kann. Kennt ihr villeicht soetwas?

Ich muss jetzt leider weg,
pointhi

[Thomas$]

http://www.youtube.com/watch?v=0ISlPVhYMl4
(http://www.youtube.com/watch?v=0ISlPVhYMl4)sicher kann man nicht sein das alle felder erwicht wurden z.b. wenn die sackgasse schon der ausgang gewesen wäre
als alternative könnte man noch eine andere markierung einführen zum markieren von kreuzungen

[pointhi]

Ich hab mal mein testlabyrint hier gezeichnet:

Grün: Startpunkt
Rot: Wird in meinem Fall nicht durchfahren

24372

Der Algorithmus: Trémaux-Algorithmus & Es wird wenn möglich nach rechts abgebogen, bzw. der rechten Wand gefolgt.

Ich versuch jetzt mit dem entdeckten Hamstersimulator einen Algorithmus zu entwickeln, oder am besten herunterzuladen um es zu testen :)
(http://www-is.informatik.uni-oldenburg.de/~dibo/hamster/simulator.html#download)

Habt ihr irgendwelche nützlichen infos oder ideen um das problem geschickt zu lösen. Das problem ist die Zeit, wenn der Algorithmus zu viele umwege macht sieht man das sicher in der zeit. Auch wenn unser Roboter zu den schnelleren zählt (letztes Jahr 1:40 für das ganze Labyrinth :) )

mfg, pointhi

- - - Aktualisiert - - -

Ich bin zum schluss gekommen dass der Trémaux-Algorithmus bei Labyrinthen mit freistehenden Wänden vermutlich nicht funktioniert. Wenn man sich das Labyrinth ausgestreckt als Baum vorstellt merkt man schnell wie der Algorithmus funktioniert. Wenn aber im Baum Äste durcheinander verbunden sind funktioniert der Algorithmus nicht mehr zuverlässig.

Der einzige für mich derzeit anwendbare Algorithmus ist der Algorithmus von Gaston Tarry.
Ich hab selber auch einen Algorithmus entwickelt, der eine Mischung aus Rechte Hand Regel, Trémaux-Algorithmus und Pathfinding (A*-Algorithmus) ist. Das zu implementieren wäre aber vermutlich wesentlich komplexer.

- - - Aktualisiert - - -

Nachtrag: Hab den Algorithmus von Gaston Tarry bei meinem Labyrinth angewendet:

Es funktioniert, man sollte aber den Gang vom Startpunkt bei der Ersten Kreuzung nicht nur mit Zuletzt sondern auch mit Stopp Markieren, und am Ende mittels Pathfinding zum Start zurückfahren. Ansonsten schaut er mir sehr effizient an.

Habt ihr noch andere Ideen zu diesem Thema? Glaube der Algorithmus von Gaston Tarry ist für Rescue B gut geeignet, und wird wohl nicht so einfach zu toppen sein.

mfg, pointhi

[Thomas$]

der Algorithmus von Gaston Tarry ist wohl der effizienteste, die anderen werden ihn wohl auch nutzen ;)
genial wäre ein Sackgassen früh-erkenn-system