javascript - 回溯递归以在二维数组中找到从源到目标的路径

Question

我试图在二维数组中找到一条可能的路径，并且我有一个源点 (x,y) 和一个目标点 (destX, destY)。

我正在尝试以回溯递归的方式进行，因为我不关心找到最短路径，我只关心找到一条路径。

问题是在算法中不知何故它会直接走到一个 Angular 落并卡在那里......所以我想我写的逻辑不正确。

递归函数:

$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;
    };

调用递归的函数，在找到路径并将其写入 bool 二维数组后，应该以图形方式打印路径:

$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");
        }
    };

请帮我找出我在算法中做错了什么。

Answer 1

问题是你会原地踏步，访问你之前已经尝试过的节点(没有成功)，然后再次尝试。

搜索永远不必两次访问同一个方 block 。因此，请记录您之前去过的地方，这样您就不会在回溯时抹掉该痕迹，并且再也不会从该方 block 开始搜索。

这可以通过在解决方案节点中添加附加属性来实现，并在使用 marked = true 标记节点之前添加这两行代码:

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