Backtracking-Rekursion, um einen Pfad von Quelle zu Ziel im 2D-Array zu finden

Question

Also versuche ich einen möglichen Pfad innerhalb 2D-Array zu finden und ich habe einen Quellpunkt (x, y) und einen Zielpunkt (destX, destY).

Ich versuche, es in einer Backtracking-Rekursion Weise zu tun, da ich mich nicht um den Kürzesten Weg kümmern, alles was ich interessiere ist einen Weg zu finden.

Das Problem ist, dass es irgendwie innerhalb des Algorithmus geht es in eine Ecke und bleibt dort stecken ... Also ich denke, ich schrieb etwas falsch logisch.

Die Rekursion Funktion:

$scope.findPath = function(x, y, destX, destY) { 
     console.log("x: " + x + ", y: " + y); 
     if(x >= $scope.buttons.length || x < 0 || y >= $scope.buttons[0].length || y < 0) { 
      return false; 
     } 

     if(x == destX && y == destY) { 
      return true; 
     } 

     if(!$scope.checkIfButtonEmpty(x, y)) { 
      console.log("location not empty") 
      return false; 
     } 

     $scope.solution[x][y].marked = true; 

     if($scope.findPath(x + 1, y, destX, destY) === true) { 
      return true; 
     } 
     if($scope.findPath(x, y + 1, destX, destY) === true) { 
      return true; 
     } 
     if($scope.findPath(x - 1, y, destX, destY) === true) { 
      return true; 
     } 
     if($scope.findPath(x, y - 1 , destX, destY) === true) { 
      return true; 
     } 

     $scope.solution[x][y].marked = false; 

     return false; 
    }; 

Die Funktion, die die Rekursion ruft und nach einem Weg zu finden und es in einen boolean 2D-Array schreiben sollte den Pfad grafisch drucken:

$scope.startDrawingConnection = function() { 
     if($scope.startLocation.length == 2 && $scope.endLocation.length == 2){ 
      $scope.findPath($scope.startLocation[0], $scope.startLocation[1], $scope.endLocation[0], $scope.endLocation[1]); 
      console.log("Finished finding path"); 
      $scope.drawPath(); 
      console.log("Finished drawing path"); 
     } 
    }; 

Bitte helfen Sie mir herauszufinden, was ich falsch im Algorithmus gemacht habe. Vielen Dank im Voraus.

Answer 1

Das Problem ist, dass Sie in Kreisen laufen werden, Knoten besuchen, die Sie bereits vorher (ohne Erfolg) ausprobiert haben, und sie erneut versuchen.

Die Suche sollte das gleiche Quadrat nie zweimal besuchen müssen. Behalte also den Überblick, wo du vorher warst, und zwar so, dass du diese Spur beim Backtracking nicht auslöschen und nie wieder eine Suche von diesem Quadrat aus starten wirst.

Dies kann man erreichen, indem eine zusätzliche Eigenschaft in Ihrer Lösung Knoten hinzufügen, und fügen Sie diese beiden Zeilen Code, kurz bevor Sie einen Knoten mit marked = true markieren:

if ($scope.solution[x][y].visited) return false; 
    $scope.solution[x][y].visited = true;