迷宫搜索算法遇到调用堆栈大小超出错误

Question

我正在尝试实现一种路径搜索算法。输入是一个迷宫，编码为矩阵，其中值1代表可以遍历的单元格，值2代表目标。给出了起点坐标。

但是我的代码存在一个问题：它遇到了超过最大调用堆栈大小错误。有什么问题吗？

function maze(myMaze) {
    this.find = function(col, row) {
        console.log(row, col, myMaze[row][col])
        if (myMaze[row][col] == 2){
            console.log('done')
        }
        if (myMaze[row][col] == 1) {
            console.log('we on the right way')
            if (row < myMaze.length - 1) {
                this.find(col, row + 1)
            }
            if (col < myMaze[row].length - 1) {
                this.find(col + 1, row)
            }
            if (row > 0) {
                this.find(col, row - 1)
            }
            if (col > 0) {
                this.find(col - 1, row)
            }
        }
    }
}

var myMaze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
var maze = new maze(myMaze)
maze.find(0, 3)

Answer 1

主要问题是你的算法在循环中运行：从单元格 B 它将访问它之前访问过的单元格 A，然后从那里它将更深地递归以再次到达单元格 B，并且这种情况永远持续下去。最终调用堆栈将耗尽内存。

这可以通过跟踪已经访问过的单元格来解决，这样它们就不会被再次访问。虽然这可以通过数组来完成，但使用

Set

会更有效。

其次，您对

maze

构造函数和

maze

实例使用相同的名称。这将导致无法连续解决两个迷宫。相反，请使用常见做法以首字母大写字母命名构造函数：

Maze

。

此外，如果您只是输出算法找到目标单元格的事实，则您没有有关找到的路径的任何信息。最好返回路径，让调用者按照自己的意愿处理。

最后，没有理由在实例上创建

find

方法：更好的做法是在原型上定义它，这样即使您创建多个迷宫实例，也只需要创建一次。

我还建议放弃旧式的构造函数并使用 ES6

class

语法，该语法已经存在了好几年了。

以下是编码方法：

class Maze {
    constructor(maze) {
        this.maze = maze;
        this.width = maze[0].length;
        this.height = maze.length;
    }
    // Added optional argument to indicate cells that should not be visited
    find(col, row, visited = new Set) { 
        // Create a unique reference for the current cell
        const cellId = row * this.width + col; 
        // Check that this cell lies within the grid, has a non-zero value, 
        //    and has not been visited before
        if (!this.maze[row] || !this.maze[row][col] || visited.has(cellId)) {
            return; // No success
        }
        visited.add(cellId); // Mark this cell as visited, so it is not visited a second time.
        //console.log("visiting: ", col, row); // Uncomment to see progress
        if (this.maze[row][col] == 2) { // Bingo!
            return [[col, row]]; // Return the path that will be extended during backtracking
        }
        // Loop through the 4 directions
        for (const [addcol, addrow] of [[0, 1],[1, 0],[0, -1],[-1, 0]]) {
            const found = this.find(col+addcol, row+addrow, visited);
            // If found, prepend current cell to partial solution and get out of recursion
            if (found) return [[col, row], ...found]; 
        }
    }
}

const myMaze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];


const maze = new Maze(myMaze);
const path = maze.find(0,3);
console.log(JSON.stringify(path));

Answer 2

我保留一个数组来跟踪已经访问过的索引。可以编辑查看要观看的路径

 var myMaze = [
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
          [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
          [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
          [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
          [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
          [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        ];

 var c_path=new Array();
 var path=new Array();
 var last ;
 function maze(myMaze){

       this.find = function(col,row){
       if(myMaze[row][col] == 1 ){
            path.push(new Array(row,col));
            console.log(row,col,myMaze[row][col])
       }
       if(myMaze[row][col] == 2){
            last =new Array(row,col);
            console.log('done')
       }
       if(myMaze[row][col] == 1 ){
            if(c_path.includes(row+"-"+col)){
                    return;
            }
            c_path.push(row+"-"+col);
            if(row < myMaze.length - 1){
                    this.find(col,row+1)
             }
             if(col< myMaze[row].length -1){
                this.find(col+1,row)
             }
             if(row > 0){
                this.find(col,row-1)
             }
             if(col > 0){
                this.find(col-1,row)
             }
        }
    }
    this.show =function(){

        for (var i = path.length-1 ;i>0 ;i--){
            var tmp =path[i];
            if((tmp[0] ==last[0] && Math.abs(tmp[1] - last[1]) ==1) ||  (tmp[1] ==last[1] && Math.abs(tmp[0] - last[0]) ==1)){

                last =tmp;
                myMaze[tmp[0]][tmp[1]] =3;
            }
        }
        console.log(myMaze);
    }
}

var maze= new maze(myMaze)
maze.find(0,3)
maze.show();