java - 深度优先搜索递归调用导致 StackOverflow 错误

问题描述

我正在使用深度优先搜索算法的实现来解决迷宫问题。我不希望找到最短路径，而是希望以最快的方式找到有效路径。这是我用来解决迷宫的方法。迷宫是 2d int 数组，其中 0 是开放的正方形，1 是墙壁，2 是访问过的正方形，9 是目的地。

    public class DepthAlgorithm {

/**
 * This method returns true when a path is found. It will also fill up the
 * list with the path used. It will start from (xn,yn,.....,x2,y2,x1,y2)
 * because it will use recursion.
 * @param maze 2d array of maze
 * @param x the x of the starting position
 * @param y the y of the starting position
 * @param path a List of the path
 * @return True if a path is found
 */
public static boolean searchPath(int [][] maze, int x, int y, List<Integer> path){
    // Check if the destination (9) is reached
    if (maze[y][x] == 9) {
        path.add(x);
        path.add(y);
        return true;
    }

    // When the current position is not visited (0) we shall make it visited (2)
    if (maze[y][x] == 0) {
        maze[y][x] = 2;

        //Here we visit all neighbour squares recursively and if a path is found
        // we shall fill the path list with the current position.
        int dx = -1;                // Start and search from starting
        int dy = 0;                 // position (x-1,y)
        if (searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 1;                    // Start and search from starting
        dy = 0;                    // position (x+1,y)
        if (searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 0;                   // Start and search from starting
        dy = -1;                  // position (x,y-1)
        if (searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }

        dx = 0;                   // Start and search from starting
        dy = 1;                   // position (x,y+1)
        if (searchPath(maze, x + dx, y + dy, path)) {
            path.add(x);
            path.add(y);
            return true;
        }
    }
    return false;
}

}

我的算法适用于小型迷宫。当我想解决一个 50 * 50 的迷宫时，它非常快。当我移动到 500 * 500 时，会出现 Stack Overflow 错误。我可以理解它是由于函数的许多递归调用而出现的，但我不知道如何修复它。有没有另一种方法让我仍然可以使用深度优先搜索并存储我的路径但没有堆栈溢出？或者是否可以在我的代码中进行任何更改以便修复？

public class MazeRunner {

// Maze is a 2d array and it has to be filled with walls peripherally
// with walls so this algorithm can work. Our starting position in this
// will be (1,1) and our destination will be flagged with a 9 which in
// this occasion is (11,8).
private int[][] maze ;
private final List<Integer> path = new ArrayList<>();
public long startTime,stopTime;

public MazeRunner(int [][] maze){
    this.maze = maze;
}

public void runDFSAlgorithm(int startingX,int startingY){
    startTime = System.nanoTime();
    DepthAlgorithm.searchPath(maze,startingX,startingY,path);
    stopTime = System.nanoTime();
    printPath();
    System.out.println("Time for Depth First Algorithm: "+((double) (stopTime-startTime) / 1_000_000)+" milliseconds");

}

public void printPath(){
    ListIterator li = path.listIterator(path.size());
    int lengthOfPath = (path.size()/2-1);
    int fromX,fromY,bool = 0,toX = 0,toY = 0,i = 2;
    while(li.hasPrevious()){
        if (bool == 0) {
            fromX = (int) li.previous();
            fromY = (int) li.previous();
            toX = (int) li.previous();
            toY = (int) li.previous();
            System.out.println("From ("+fromY+", "+fromX+") to ("+toY+", "+toX+")");
            bool++;
            continue;
        }
        if (bool == 1){
            fromX = toX;
            fromY = toY;
            toX = (int) li.previous();
            toY = (int) li.previous();
            System.out.println("From ("+fromY+", "+fromX+") to ("+toY+", "+toX+")");
            i++;
        }
    }
    System.out.println("\nLength of path is : "+lengthOfPath);
}

public static void main(String[] args){
    int [][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1},
                     {1,0,1,0,1,0,1,0,0,0,0,0,1},
                     {1,0,1,0,0,0,1,0,1,1,1,0,1},
                     {1,0,0,0,1,1,1,0,0,0,0,0,1},
                     {1,0,1,0,0,0,0,0,1,1,1,0,1},
                     {1,0,1,0,1,1,1,0,1,0,0,0,1},
                     {1,0,1,0,1,0,0,0,1,1,1,0,1},
                     {1,0,1,0,1,1,1,0,1,0,1,0,1},
                     {1,0,0,0,0,0,0,0,0,0,1,9,1},
                     {1,1,1,1,1,1,1,1,1,1,1,1,1}};
   MazeRunner p = new MazeRunner(maze);
   p.runDFSAlgorithm(startingPoint[0],startingPoint[1]);
}

}

这是我用于测试的课程。它肯定适用于此示例，但对于更大的数组则无效。任何建议将不胜感激。当我在大数组上运行程序时，出现以下错误：

标签： javarecursionstack-overflowdepth-first-searchmaze

java - 深度优先搜索递归调用导致 StackOverflow 错误

问题描述

解决方案

推荐阅读