迷宫递归解决StackOverflow错误

Question

我正在尝试使用递归来解决迷宫问题.它被宣布了Cell [][] maze.

public class Cell {
    private Wall left;
    private Wall right;
    private Wall up;
    private Wall down;
    private boolean end;

    // Setters and getters not shown
}

如果Wall单元格的某一侧没有,那么它有值null,否则它指的是一个Wall对象.Wall参考是一致的:与单壁相邻的两个单元都用适当的字段表示它.如果缺少墙,则两个相邻的单元都具有相应的null条目.这是搜索:

public boolean solveMaze(Cell[][] maze, int i, int j) {

    if (maze[i][j].isEnd()){
        System.out.println(maze[i][j].toString());
        return true;
    }
    if (maze[i][j].getDown() == null) {
        return solveMaze(maze, i, j + 1); 
    }
    if (maze[i][j].getUp() == null) {
        return solveMaze(maze, i, j - 1) ;
    }
    if (maze[i][j].getLeft() == null) {
        return solveMaze(maze, i - 1, j);
    }
    if (maze[i][j].getRight() == null) {
        return solveMaze(maze, i + 1, j) ;  
    }
    return false;
}

我收到了一个Stack Overflow错误.我的递归停止条件有什么问题？

更新:

有了您非常感谢的帮助,我解决了这个问题:这是正确无误的解决方案:

public boolean solveMaze(Cell[][] maze, int i, int j){

    if (maze[i][j].isEnd()){
        System.out.println("Maze Exit :["+i+","+j+"]" );
        return true;
    }

    if (maze[i][j].isVisited()){
        return false;
    }

    maze[i][j].setVisited(true);

    if ((maze[i][j].getButtom() == null) ){
        if (solveMaze(maze,i,j+1)==true)
            return true;
    }

    if ((maze[i][j].getUp() == null) ){
    if ( solveMaze(maze,i,j-1) ==true )
        return true;
    }

    if ((maze[i][j].getLeft() == null)){
        if (solveMaze(maze,i-1,j))
            return true;
    }

    if ((maze[i][j].getRight() == null)){
        if (solveMaze(maze,i+1,j)) 
            return true;
    }

    maze[i][j].setVisited(false);
    return false;
} 

可能对未来的任何机构都有帮助.

Answer 1

如果迷宫有一个循环,求解器可以永远围绕这个循环运行,这将导致你看到的堆栈溢出.您需要一种方法来确定何时看到已经看过的迷宫广场.在这种情况下,您应该立即回溯.

这可以用一个布尔标志来完成visited在初始设置为false,然后为每个搜索广场设置为true,或者可以保持一个单独的每个单元Set的(i,j)已经检索,这最初是空的对.

注意:你的使用i和j非常规.如果其他人用常规用法编写了迷宫阅读代码,这可能会导致问题.在数学中,i通常用于行号和j列.根据此惯例,您的墙壁测试不同意您的增量和减量.缺少底壁会要求您增加i例如.

Answer 2

在我看来,就像你在解算器方法中运行一样.
我建议你熟悉广度优先搜索,这通常用于不太大的状态搜索问题.

如果你有一些"知识",一个启发式,如何搜索迷宫,那么你也可以看看A-Star搜索

在你的情况下,BFS可以做的是:(顺便说一句,很好,并使用适当的建设者,吸气剂和制定者)

public class Cell {
    public int x;
    public int y;
    public Cell parent;

    @Override
    public boolean equals(Object obj) {
        // TODO Override equals so it only incudes x and y coorinates, and not parent
        return true;
    }

    @Override
    public int hashCode() {
        // TODO Override hash code as well
        return 0;
    }
}

public Cell seachFor(Cell start, Cell finish) {
    Queue<Cell> open = new LinkedList<>();
    Set<Cell> closed = new HashSet<>();

    open.add(start);

    while (!open.isEmpty()) {
        Cell current = open.poll();
        if (current.equals(finish)) {
            return current;
        }

        closed.add(current);

        for (Cell neighbour : getNeighbours(current)) {
            if (!closed.contains(neighbour)) {
                open.add(neighbour);
            }
        }
    }

    return null;

}

private List<Cell> getNeighbours(Cell current) {
    /* TODO Set the neighbour's "parent"
     * Return valid adjacent neighbour cells
     */
    return null;
}

public Deque<Cell> pathfinder(Cell start) {
    Deque<Cell> path = new ArrayDeque<>();
    path.push(start);

    Cell current = start;

    while (current.parent != null) {
        current = current.parent;
        path.push(current);
    }

    return path;
}

public static void main(String[] args) {
    Cell start = maze.getStart();
    Cell finish = maze.getFinish();
    Deque<Cell> path = pathFinder(searchFor(start, finish))
    while (!path.isEmpty()) {
        Cell current = path.pop();
        maze.moveTo(current);
    }
}

请注意,这是一个模拟代码,您需要在它工作之前对其进行优化.