Hallo

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

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

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

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

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.

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!

Hallo!
Ich habe vor kurzem erst einen kleinen Text für die Informatikerstsemester über das 8 Damen-Problem geschrieben. Ihr könnt ja mal reinschauen:

http://www2.informatik.uni-wuerzburg.../12/8damen.pdf
Falls noch Fragen offenbleiben sagt Bescheid.

Gruss,
Stephan

Hmm, das 8-Dame-Problem hilft Dir zwar die Rekursion anzuwenden und zu verstehen, hilft aber ansonsten nicht weiter beim Labyrinth-Problem, denk ich mal.

"Dijkstra" hilft meines Wissens auch nur dann, wenn alle n möglichen Wege bereits bekannt sind und anschließend sucht man sich aus diesen n Wegen den kürzesten heraus, oder? Ist aber recht gut, wenn man die Wege mal hat.

Also ich würde den Weg durchs Labyrinth so suchen (stark vereinfacht natürlich und unsere Methode soll FindPath() heissen):

1.) Ersten Schritt machen ins Labyrinth von außerhalb der Methode: FindPath(geradeaus)

In der Methode FindPath():
2.) Wenn Weg nach links frei: FindPath(links)
3.) Wenn Weg nach rechts frei: FindPath(rechts)
4.) Wenn Weg geradeaus frei: FindPath(geradeaus)
5.) Wenn Weg blockiert: Methode beenden

Natürlich muss man sich dabei immer den zurückgelegten Weg merken, man könnte ja in einem mehrdimensionalen Array die Wegentscheidungen wegsichern.

Das wäre so mein erster Ansatz ...

Hallo,

vielleicht willst dir ja ansehen wie es andere gelöst haben.

C# Corner: Maze Solver

Mfg,
Alex

Natürlich muss man sich dabei immer den zurückgelegten Weg merken, man könnte ja in einem mehrdimensionalen Array die Wegentscheidungen wegsichern.

Aber nur wenn man hinterher den Weg noch ausgeben will. Wenn nur die Lösung gefunden werden soll, dann ist der Weg uninteressant.

@Saber:
Was mich auf den Dijkstra gebracht hat, ist die Tatsache, dass er den kürzesten Weg finden soll, und dafür müssen ja alle möglichen Wege schon bekannt sein.
Es gibt vom Dijkstra auch noch eine FIFO Variante die unter bestimmten Bedingungen schneller ist.

Danke erstmal für die vielen Antworten.

Ich glaube so langsam verstehe ich das ganze.

Kleiner Tipp noch... Diese Methode macht man am besten static - oder?