Backtracking für Newbies?

S

sra

Erfahrenes Mitglied
Hallo

Was ich suche ist eine Erklärung von Backtracking, die sogar ich verstehe :D

Ich meine. das Grundprinzip habe ich geschnallt, aber wo es bei mir noch happert ist beim "sich das ganze vorstellen".

Wenn ich zum Beispiel durch ein Labyrinth muss, und in einer Sackgasse stecke, wie zum Teufel merkt die Methode dann, bis wo sie zurück muss?

Arbeitet man da mit Eigenschaften, das für jedes Feld im Labyrith die bereits versuchten Wege speichert, oder was...?

Ihr seht - ich sehe da noch nicht ganz durch :D
 
Ich glaube man könnte das recht gut mit Rekursion lösen. Eine Methode ruft sich immer und immer wieder selber auf, bis sie "ansteht" und nicht mehr weiter kann. Der Compiler managed das ganze dann so, dass er in die aufrufende Methode zurückkehrt und dort weitermacht. Im Prinzip wird für jede Abzweigungsmöglichkeit eine eigene Instanz dieser Methode aufgerufen ... und zwar so lange, bis Du den Weg durchs Labyrinth hast.

Ich denke so könnte man das ganze recht einfach lösen. Ich glaube für solche Probleme dürfte es bei Google eine Menge zu finden geben, z.B. optimiertere Suchvorgänge, bei denen das Programm versucht herauszufinden, ob ein Weg überhaupt richtig sein kann etc.
 
Genau so wie Saber das beschrieben hat, funktioniert es. In dem Labyrinth wird einfach an jeder Position nachgesehen, in welchen Richtungen es noch weitergeht und eine davon wird eingeschlagen. Beim nächsten Feld passiert das gleiche nochmal. Und wenn man irgendwann an einem Feld angekommen ist, an dem es in keine Richtung mehr weitergeht, geht man die Rekursion so weit rückwärts, bis man eine andere Richtung ausprobieren kann.
Und so geht das dann immer weiter, bis man irgendwann den Weg aus dem Labyrinth heraus gefunden hat. Im Grunde ist das also nichts anderes als immer wieder Entscheidungen treffen und bei der falschen Entscheidung so weit zurückgehen, bis man noch weitere Optionen offen hat.
 
Backtracking ist nichts anderes als eine Art der Rekursion.

Es gibt da dieses bekannte Damen-Problem, dass man in google sehr schnell findet, allerdings habe ich über google keine Erklärung gefunden, bei welcher es bei mir entgültig "klick" gemacht hat :D

Ich weiss in etwa wie es geht, aber es ist enorm abstrakt, und ich habe den überblick nicht so wirklich.
 
Es gibt da dieses bekannte Damen-Problem, dass man in google sehr schnell findet, allerdings habe ich über google keine Erklärung gefunden, bei welcher es bei mir entgültig "klick" gemacht hat :D
Zum Vergrößern anklicken....
Das Springer-Problem ist meiner Meinung nach leichter zu verstehen, und im Grunde auch nichts anderes als eine Art Labyrinth. :)
 
Was noch dazukommt ist, dass ich nicht einen weg aus dem Labyrinth brauche, sondern den schnellsten. Also muss ich wirklich alle Varianten durchmachen, und jedesmal wenn ich zum ende komme die anzahl felder speichern, und dann wieder weitermachen.

Ich weiss wie es in der theorie geht, aber schwierig wird es dann, wenn man sich vorstellt, dass die funktion wieder und wieder und wieder aufgerufen wird.

Woher weiss denn die rekursive Schleife, dass man (wenn man im labyrinth irgendwo steht) hier und hier schon versucht hat? muss man das speichern (in ner variable), oder merkt die schleife das "selber"?
 
Wenn Du die rekursive Methode so programmierst, dass sie alle vorhandenen Möglichkeiten durchläuft und nicht beim ersten gefunden Weg abbricht, dann erhältst Du alle Wege. Allerdings wirds dann schon ein bisschen komplizierter, denn Du musst Dir die Anzahl der Schritte speichern, und zwar für jeden Weg. Endet ein Weg in einer Sackgasse, dann muss der Zähler bis zur letzten Verzweigung zurückgesetzt werden. Genauso muss der Zähler bei einem korrekten Weg zurückgesetzt werden, das Zwischenergebnis muss aber weggesichert werden.
Wenn Du die Route auch haben willst musst Du Dir ebenfalls die Entscheidungen sichern, also ob das Programm nach links, rechts, gerade aus marschiert ist.

So würds ich mal versuchen nach einem ersten Brainstorming-Versuch. ;)
 
Was noch dazukommt ist, dass ich nicht einen weg aus dem Labyrinth brauche, sondern den schnellsten. Also muss ich wirklich alle Varianten durchmachen, und jedesmal wenn ich zum ende komme die anzahl felder speichern, und dann wieder weitermachen.
Zum Vergrößern anklicken....

Dann such mal lieber nach dem Dijkstra Algorithmus. Da findest du den kürzesten Weg unter Beachtung aller möglichen Wege - ich hab für's Studium mal einen Roboter programmiert, der aus einem Labyrinth findet.
 
Oh - hab noch was wichtiges vergessen:
Dijkstra geht natürlich nur wenn dein Labyrinth schon bekannt ist!
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück