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%B6...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
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