英文:
Depth First Search recursive calls cause StackOverflow error
问题
以下是您提供的内容的中文翻译：
我正在使用深度优先搜索算法的实现来解决迷宫问题。我不希望找到最短路径，而是希望找到找到有效路径的最快方法。这是我用来解决迷宫问题的方法。迷宫是2D整数数组，其中0表示空白方块，1表示墙壁，2表示访问过的方块，9表示目标。
public class DepthAlgorithm {
/**
* 当找到路径时，此方法返回true。它还将路径填入列表中。它将从（xn,yn,.....,x2,y2,x1,y2）开始，因为它会使用递归。
* @param maze 迷宫的二维数组
* @param x 起始位置的x坐标
* @param y 起始位置的y坐标
* @param path 路径的列表
* @return 如果找到路径则返回true
*/
public static boolean searchPath(int [][] maze, int x, int y, List<Integer> path){
// 检查是否到达目标（9）
if (maze[y][x] == 9) {
path.add(x);
path.add(y);
return true;
}
// 当前位置为未访问状态（0）时，将其标记为已访问（2）
if (maze[y][x] == 0) {
maze[y][x] = 2;
// 在这里，我们递归地访问所有相邻方块，如果找到路径，我们将填充路径列表
int dx = -1; // 从起始位置开始搜索
int dy = 0; // 位置为 (x-1,y)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
dx = 1; // 从起始位置开始搜索
dy = 0; // 位置为 (x+1,y)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
dx = 0; // 从起始位置开始搜索
dy = -1; // 位置为 (x,y-1)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
dx = 0; // 从起始位置开始搜索
dy = 1; // 位置为 (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的迷宫时，会出现堆栈溢出错误。我理解这是因为函数的递归调用太多，但我不知道如何解决。**是否有另一种方法，我仍然可以使用深度优先搜索并存储路径，但不会出现堆栈溢出？或者是否可以对代码进行一些更改以修复这个问题？**
public class MazeRunner {
// 迷宫是一个二维数组，必须在周边用墙壁填充，以使该算法能够正常工作。我们的起始位置在此情况下为(1,1)，目标位置标记为9，即(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("深度优先算法用时： "+((double) (stopTime-startTime) / 1_000_000)+" 毫秒");
}
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("从 ("+fromY+", "+fromX+") 到 ("+toY+", "+toX+")");
bool++;
continue;
}
if (bool == 1){
fromX = toX;
fromY = toY;
toX = (int) li.previous();
toY = (int) li.previous();
System.out.println("从 ("+fromY+", "+fromX+") 到 ("+toY+", "+toX+")");
i++;
}
}
System.out.println("\n路径长度为: "+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,
<details>
<summary>英文:</summary>
I mam using an implementation of the Depth First Search Algorithm in order to solve a maze. I do not wish for the shortest path to be found but for the fastest way to find a valid path. This is the method i use to solve mazes. Mazes are 2d int arrays where 0 is an open square, 1 is a wall, 2 is a visited square and 9 is the destination.
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;
}
}
My algorithm works fine for small maze sizes. When i want to solve a 50 * 50 maze it's quite quick. When i move to 500 * 500 a Stack Overflow error shows up. I can understand that it shows up because of the many recursive calls of the function but i do not know how to fix it. **Is there another way so I can still use the Depth First Search and store my path but without the Stack Overflow? Or are there any changes that can be done in my code so it can be fixed?**
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]);
}
}
And this is the class i use for my testings. It for sure works for this example but for greater arrays it doesn't. **Any suggestions would be appreciated**. When i run my program on big arrays i get this following error:
[![error messages][1]][1]
[1]: https://i.stack.imgur.com/HTv5v.png
</details>
# 答案1
**得分**: 1
一般来说，导致堆栈溢出异常的可能性只有两种：
1. 堆栈内存不足
2. 存在一个死循环，而且在使用递归时没有存在终止条件。
由于您的算法在小尺寸迷宫上有效，很可能是第一种情况。正如您所知，递归的规则是先进后出，在Java虚拟机（JVM）中，所有未执行函数的数据将存储在堆栈中，而堆栈拥有比堆更小的内存。
<details>
<summary>英文:</summary>
Generally speaking there are only two possibilities that could cause a stackoverflow exception
1.memory of stack is not enough
2.there exist a dead loop which in using recursive means it does't exist an end condition.
Since you algo works for small size maze. It’s possible the reason one. As you know the rule of recursive is first in last out, in JVM all the data of unexecuted functions will be stored in stack which owns a much smaller memory than heap.
</details>
# 答案2
**得分**: 1
你在实际工作中不应该使用递归算法，除非你确定堆栈的深度会被限制在合理的范围内。通常情况下，这意味着O(log N)，或者最多是O(log^2 N)。
对于一个500x500的迷宫，使用深度优先搜索（DFS）可能会在堆栈上产生大约25万次函数调用，这太多了。
如果你真的想使用DFS，但你应该在一个单独的数据结构中维护自己的堆栈。不过，广度优先搜索（BFS）可能会更好，除非你真的不希望得到最短路径。
<details>
<summary>英文:</summary>
You should never use a recursive algorithm for real work unless you know for certain that the depth of the stack will be limited to a reasonable number. Usually that means O(log N), or O(log^2 N) at most.
DFS for a 500x500 maze could put around 250000 function calls on the stack, which is way too many.
You can use DFS if you really want to, but you should maintain your own stack in a separate data structure. BFS would be better though, unless there's some reason you really don't want the shortest path.
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论