如何避免递归迷宫求解器中的堆栈溢出错误

Question

像大学里许多其他Java学生一样，我需要开发一个解决迷宫的迷宫程序。实现递归的 solveMaze 方法返回了堆栈溢出运行时错误。请问我该如何解决这个问题？这与我的算法有关吗？提前谢谢。

A( 我创建了一个解决方案迷宫，该阵列将保存通往出口的路径。

B( 然后，我实现了一种方法solveMaze()，每次调用它时都向出口迈出一步。

注意：isWall() 方法检查您要移动到的位置是否是墙壁。

  public void showPath() {
    int[][] sol = new int[m.length][m[0].length];
    for (int j = 0; j < sol.length; j++) {
      for (int i = 0; i < sol[0].length; i++) {
        sol[j][i] = m[j][i];
      }
    }
    if (solveMaze(sol, m.length - 1, 0, exitCords) == false)
      System.out.println("Solution doesn't exist");
    else {
      for (int y = 0; y < sol.length; y++) {
        for (int x = 0; x < sol[0].length; x++) {
          if (sol[y][x] == exitCords[0] && sol[y][x] == exitCords[1]) {
            System.out.print("E ");
          } else {
            if (sol[y][x] == 1) {
              System.out.print("  ");
            } else if (sol[y][x] == 3) {
              System.out.print("~");
            } else {
              System.out.print("# ");
            }
          }
        }
        System.out.println();
      }
    }
  }
  public boolean solveMaze(int[][] sol, int y, int x, int[] exitCords) {
    //exitCords[] is a one-dimensional array that holds the x and y coordinate of the exit point on a maze.
    if (y == exitCords[1] && x == exitCords[0]) {//Base Case
      return true;
    }
    //North
    if (!isWall(x, y - 1) && sol[y - 1][x] != 3) {
      sol[y][x] = 3;//3 is assigned to positions you already visited.
      y--;
      sol[y][x] = 3;
      //Implement recursion to call the solveMaze again on this line.
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    //South
    else if (!isWall(x, y + 1) && sol[y + 1][x] != 3) {
      sol[y][x] = 3;
      y++;
      sol[y][x] = 3;
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    //East
    else if (!isWall(x + 1, y) && sol[y][x + 1] != 3) {
      sol[y][x] = 3;
      x++;
      sol[y][x] = 3;
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    //West
    else if (!isWall(x - 1, y) && sol[y][x - 1] != 3) {
      sol[y][x] = 3;
      x--;
      sol[y][x] = 3;
      solveMaze(sol, y, x, exitCords);
      return true;
    }
    /*The following line of code are to get out of dead ends and replace every position near a dead end with a wall*/
    else if ((isWall(x, y - 1) && isWall(x, y + 1) && isWall(x + 1, y)) || (isWall(x, y - 1) && isWall(x, y + 1) && isWall(x - 1, y))
        || (isWall(x - 1, y) && isWall(x, y + 1) && isWall(x + 1, y)) || (isWall(x - 1, y) && isWall(x, y - 1) && isWall(x + 1, y))) {
      if (isWall(x, y - 1) && isWall(x, y + 1) && isWall(x + 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y, x - 1, exitCords);
        return true;
      }
      if (isWall(x, y - 1) && isWall(x, y + 1) && isWall(x - 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y, x + 1, exitCords);
        return true;
      }
      if (isWall(x - 1, y) && isWall(x, y + 1) && isWall(x + 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y - 1, x, exitCords);
        return true;
      }
      if (isWall(x - 1, y) && isWall(x, y - 1) && isWall(x + 1, y)) {
        sol[y][x] = 0;
        solveMaze(sol, y + 1, x, exitCords);
        return true;
      }
    }
    return false;
  }

Answer 1

您有不同的方法来解决问题：

• 第一个是在不使用递归的情况下重写代码(尾递归没有运气 - Java 没有针对它的优化(
• 另一种方法是使用-Xss选项增加堆栈大小
• 或者，您可以将实际深度检查添加到solveMaze方法中，例如：

  public void showPath() {
    // ...
    if (solveMaze(sol, m.length - 1, 0, exitCords , 0) == false) {
    // ...
  }
  public boolean solveMaze(int[][] sol, int y, int x, int[] exitCords, int depth) {
    if (depth > 64) {
      return false;
    }
    // ...
    solveMaze(sol, y, x, exitCords, depth + 1); 
    // ...  
  }

Answer 2

堆栈溢出错误意味着您的递归超出了语言允许的范围。 对于小型迷宫，这不应该发生，除非您要重新访问迷宫中的位置。 由于您的代码似乎没有做出任何努力来避免这种情况，因此您可能需要解决此问题。