Entwickler-Ecke :: Thema anzeigen - Labyrinth mit Backtracking

Hennar - Do 11.11.10 17:31
Titel: Labyrinth mit Backtracking

Hallo Zusammen,
Wir haben in der Schule gerade in Informatik die wohl allen bekannten Labyrinthe.
Bisher haben wir das sogelöst, dass man immer rechts oder links an der wand bleibt um das
Ziel zu finden.
Nun sind aber Schleifen im Labyrinth.
Labyrinth_mit_schleifen

Wenn man nun immer rechts bleiben würde, würde man irgendwann zwangsläufig im Kreis laufen.
Im Internet hatte ich nun vorher etwas zum Thema Backtracking gelesen,
hab dies jedoch nicht richtig verstanden.
Geht das damit überhaupt ?
Und wenn ja, gibts nen vielleicht nen kleinen Tipp, der mir auf die Sprünge helfen könnte wie das ganze geht ?
Für Hilfe wär ich sehr dankbar
Grüße Hennar

Flamefire - Do 11.11.10 17:54

"Immer rechts bleiben" ist eine Tiefensuche. Die funktioniert, wenn du in einer Ecke beginnst und in einer anderen endest immer. Auch n Bsp geht damit. Wo ist das das Problem?
Alternative ist die sogannte Breitensuche. Danach kannst du mal suchen.
A* ist dann das Optimum, aber etwas schwer für den Anfang

Hennar - Do 11.11.10 18:20

Problem ist wenn ich rechts am Rand lang gehe,
und dort keine Wand ran geht, dann läuft er einmal rechts an der Wand außen im Kreis und kommt dann aber nie in den Innenraum wo das Ziel ist;)

Hennar - Do 11.11.10 18:34

Ich weiß das ist mir eben auch Aufgefallen,
jedoch soll die Lösung mit Backtracking realisiert werden,
denn es könnte ja auch ein anderes Labyrinth sein.
Ich dachte mir das also so:
Gehe so lange rechts bis du
1. nicht mehr vor, links, rechts, gehen kannst, also Sackgasse.
2. auf ein Feld triffst auf dem du schonmal warst.

Dann gehe solange zurück bis du auf ein anderes Feld kannst auf dem du noch nicht warst.

Martok - Do 11.11.10 18:42

Die Idee bei Backtracking ist ja, JEDEN Weg zu versuchen.
Dabei geht man von einem Feld zuerst auf ein Nachbarfeld und guckt, ob man, von dort aus zum Ziel kommt. Wenn nicht, probiert man das nächste Nachbarfeld. Kommt man mit gar keinem weiter, teilt man das über einen Rückgabewert dem aufrufenden mit und übergibt diesem wieder die Kontrolle (=macht einen Schritt zurück, "tracking back").
Dabei verwendet man rekusrive Aufrufe, so dass von jedem Feld aus alle Wege probiert werden.

Und natürlich auch hier ein Feld mitführen, um Zellen nicht mehrmals zu besuchen.

F34r0fTh3D4rk - Do 11.11.10 19:46

Luckie hat folgendes geschrieben :

also wenn ich bei deinem Beispiellabyrinth immer rechts gehe, so dass die Wand immer rechts ist, dann komme ich zum Ziel.

Das gilt immer. Man kann nicht in einen Kreis geraten, es sei denn, es gibt keinen Weg zum Ziel, aber dann landet man irgendwann wieder am Anfang.

Kha - Do 11.11.10 20:26

Nope,

Hennar hat schon recht: Das funktioniert nicht immer.

http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower hat folgendes geschrieben:

If the maze is not simply connected (i.e. if the start or endpoints are in the center of the structure or the pathways cross over and under each other), this method will not be guaranteed to help the goal to be reached.

Hennar - Do 11.11.10 20:27

Ja, ich muss gestehen,
mir scheint es im Moment auch so, nur im Unterricht ging das irgendwie nicht, aber naja ;)
Könnte mir denn mal jemand nen Beispiel geben wie das aussehen müsste, das man sich immer rechts hält,
weil mit unserem bisherigem code (kann ihn leider gerade nicht einfügen) ging es irgendwie nicht :/

F34r0fTh3D4rk - Do 11.11.10 21:03

Kha hat folgendes geschrieben :

Nope,

Hennar hat schon recht: Das funktioniert nicht immer.

http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower hat folgendes geschrieben:

Das heißt nicht, dass es einen Kreis gibt. Ich bin jetzt auch von ganz normalen Labyrinthen ausgegangen.

Kha - Do 11.11.10 21:33

Natürlich besitzt der Graph dann einen Kreis, sonst würde das Verfahren ja nicht fehlschlagen. Sobald man an den Startpunkt zurückgelangt, ist es selbstverständlich trotzdem klüger, einfach abzubrechen :) .
Um die deutsche Wikipedia noch ins Boot zu holen:

http://de.wikipedia.org/wiki/Irrgarten#Analyse_und_L.C3.B6sung_von_Irrwegesystemen hat folgendes geschrieben:

Die Regel ist zwar einfach zu merken und kann auch vom Zielplatz aus zur Suche des Ausgangs angewendet werden, sie funktioniert jedoch nur in Anlagen, deren Ziel mit der Außenhecke verbunden ist. Liegt das Ziel in einer Insellage (Wegeschlaufe), versagt die Methode immer. Vom Eingang aus erreicht der Wanderer das Ziel niemals, er kehrt vielmehr zum Ausgangspunkt zurück; vom Zielplatz aus geht er ebenfalls „im Kreis“ und bleibt ewig gefangen.

F34r0fTh3D4rk hat folgendes geschrieben :

Ich bin jetzt auch von ganz normalen Labyrinthen ausgegangen.

Ich bin von der Aufgabenstellung ausgegangen ;) .

F34r0fTh3D4rk - Do 11.11.10 22:53

Es darf also von einem Labyrinth, wie dem aus meinem Anhang ausgegangen werden?

Backtracking [http://de.wikipedia.org/wiki/Backtracking] funktioniert prinzipiell genauso wie Floodfill [http://de.wikipedia.org/wiki/Floodfill]. Tiefensuche [http://de.wikipedia.org/wiki/Tiefensuche] ist auch etwa das gleiche.

Als weiteren Algorithmus kannst du dir auch den Dijkstra-Algorithmus [http://de.wikipedia.org/wiki/Dijkstra-Algorithmus] anschauen.

alzaimar - Fr 12.11.10 08:44

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Procedure FindeWegImLabyrinth (Labyrinth, BisherigerWeg, Position);
Begin
  AlleNaechstenSchritte := ErzeugeMoeglicheNaechsteSchritte (Labyrinth, Position)
  if AlleNachstenSchritte.IsEmpty Then
    "Sackgasse"
  Else
    Foreach NeuePosition in AlleNaechstenSchritte Do
      If Not NeuePosition in BishererWeg then
        If NeuePosition = Labyrinth.Ziel Then
          "Gefunden"
        Else 
           FindeWegImLabyrinth (Labyrinth, BisherigerWeg+NeuePosition, NeuePosition)
End;

...
// Starten:
FindeWegImLabyrinth (Labyrinth, [], Labyrinth.Start)

IsNull - Mo 15.11.10 12:11

Wie von Luckie bereits vorgeschlagen - ein Labyrinth schreit nach A*, oder einem der Derivate dessen.

Hier ist er wunderbar beschrieben, und mehr als etwas List-Handling muss man nicht mal können, sollte also einfach zu implementieren sein: http://www.policyalmanac.org/games/aStarTutorial.htm

Ich habe den anhand obiger Anleitung vor geraumer Zeit mal in AHK implementiert:
http://de.autohotkey.com/forum/topic4152.html

Und selbst mit den begrenzten Möglichkeiten der Skriptsprache funktioniert das ganz ok.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!