-         

Ergebnis 1 bis 4 von 4

Thema: effizienter Algorithmus um alle Felder eines Irrgarten zu besuchen

  1. #1
    Erfahrener Benutzer Fleißiges Mitglied Avatar von pointhi
    Registriert seit
    18.03.2009
    Alter
    22
    Beiträge
    139

    Frage effizienter Algorithmus um alle Felder eines Irrgarten zu besuchen

    Anzeige

    SMARTPHONES & TABLETS-bis zu 77% RABATT-Kostenlose Lieferung-Aktuell | Cool | Unentbehrlich
    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
    Theorie ist, wenn man alles weiß, aber nichts funktioniert.
    Praxis ist, wenn alles funktioniert, aber niemand weiß warum.
    Microsoft hat Theorie und Praxis vereint: Nichts funktioniert und keiner weiß warum!
    Deshalb nutze ich Linux für die wichtigen sachen

    Meine Website: www.oe5tpo.com

  2. #2
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    30.12.2008
    Beiträge
    1.418
    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
    Geändert von Thomas$ (29.01.2013 um 20:37 Uhr)
    was gibt es noch zu sagen

  3. #3
    Erfahrener Benutzer Fleißiges Mitglied Avatar von pointhi
    Registriert seit
    18.03.2009
    Alter
    22
    Beiträge
    139
    Ich hab mal mein testlabyrint hier gezeichnet:

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

    Klicke auf die Grafik für eine größere Ansicht

Name:	labyrinth01gross.png
Hits:	6
Größe:	3,3 KB
ID:	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-oldenbu....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
    Theorie ist, wenn man alles weiß, aber nichts funktioniert.
    Praxis ist, wenn alles funktioniert, aber niemand weiß warum.
    Microsoft hat Theorie und Praxis vereint: Nichts funktioniert und keiner weiß warum!
    Deshalb nutze ich Linux für die wichtigen sachen

    Meine Website: www.oe5tpo.com

  4. #4
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    30.12.2008
    Beiträge
    1.418
    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
    was gibt es noch zu sagen

Ähnliche Themen

  1. Effizienter 6-A-Schaltregler
    Von Roboternetz-News im Forum Neuigkeiten / Technik-News / Nachrichten / Aktuelles
    Antworten: 0
    Letzter Beitrag: 12.05.2011, 15:00
  2. ADC - Überspannung eines AIN beeinflusst alle anderen AIN
    Von Kaiser-F im Forum PIC Controller
    Antworten: 27
    Letzter Beitrag: 13.09.2010, 22:00
  3. Effizienter Rechnen?
    Von BASTIUniversal im Forum Basic-Programmierung (Bascom-Compiler)
    Antworten: 7
    Letzter Beitrag: 02.01.2008, 18:54
  4. Such Algorithmus zum ausfüllen eines Objekts mit einer Farbe
    Von p_mork im Forum Software, Algorithmen und KI
    Antworten: 13
    Letzter Beitrag: 29.07.2007, 12:45
  5. felder in bascom
    Von keha im Forum Basic-Programmierung (Bascom-Compiler)
    Antworten: 2
    Letzter Beitrag: 24.02.2007, 14:27

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •