Backtracking für Newbies?

[Saber]

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

 

[Alexander Schuc]

Hallo,

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

C# Corner: Maze Solver

Mfg,
Alex

 

[fluessig]

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.

 

[sra]

Danke erstmal für die vielen Antworten.

Ich glaube so langsam verstehe ich das ganze.

 

[sra]

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

 

[sra]

Ich hab da mal was gemacht:

using System;
namespace sonja
{
  class Class1
  {
    [STAThread]

    public static void Main(string[] args)
    {
      int actTime = 0;
      findBestPath('r', actTime);
      Console.WriteLine(bestTime);
      Console.ReadLine();
      Console.ReadLine();
    }

    static char[,] Lab = {{'A','5','4','7','6'},
                {'1','X','5','X','2'},
                {'9','4','6','7','9'},
                {'1','X','9','1','1'},
                {'7','9','3','7','E'}};

    static int x=0, y=0, bestTime=0;

    public static bool findBestPath(char compass, int actTime)
    {
      switch(compass)
      {
        case 'r': if((x+1) <= 4 && Lab[x+1,y] != 'X') { x++; actTime += Convert.ToInt32(Lab[x,y]); }  break;
        case 'u': if((y+1) <= 4 && Lab[x,y+1] != 'X') { y++; actTime += Convert.ToInt32(Lab[x,y]); } break;
        case 'l': if((x-1) <= 4 && Lab[x-1,y] != 'X') { x--; actTime += Convert.ToInt32(Lab[x,y]); } break;
        case 'o': if((y-1) <= 4 && Lab[x,y-1] != 'X') { y--; actTime += Convert.ToInt32(Lab[x,y]); } break;
        default: return (false);
      }

      if(Lab[x,y] == 'E')
      {
        if(actTime < bestTime)
        {
          bestTime = actTime;
        }
        return (false);
      }

      if(findBestPath('r', actTime)){ }
      if(findBestPath('u', actTime)){ }
      if(findBestPath('l', actTime)){ }
      if(findBestPath('o', actTime)){ }
      return (false);
    }
  }
}

Der Fehler ist, dass es einen Stack-Overflow gibt. Aber ich hab doch ein "return(ffalse)", als abbruchbedingung, wenn er überall durch ist?

Hat jemand ne Idee?