4

我正在尝试使用递归解决迷宫。它被宣布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，则它具有 value 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;
}

将来可能对任何机构都有帮助。

4

5 回答 5

8

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

这可以通过将visited每个单元格中的布尔标志初始设置为 false 然后为您搜索的每个方格设置为 true 来完成，或者您可以维护一个单独Set的(i,j)已搜索对，最初为空。

注意：您对iand的使用j是非常规的。如果其他人使用常规用法编写迷宫阅读代码，这可能会导致问题。在数学中，i通常用于行号和j列。使用此约定，您的墙壁测试与您的增量和减量不一致。例如，缺少底墙将需要您增加i。

于 2012-07-13T21:14:40.333 回答
6

在我看来，您似乎在求解器方法中绕圈子。
我建议您熟悉广度优先搜索，它通常用于不太大的状态搜索问题。

如果你有一些关于如何搜索迷宫的“知识”，一种启发式方法，那么你也可以看看A-Star Search

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);
    }
}

请注意，这是一个模拟代码，您需要在它工作之前对其进行改进。

于 2012-07-13T21:11:38.213 回答
1

您的代码中没有任何内容可以检测您以前去过的地方。如果您的迷宫包含任何您可以绕一圈或循环回到您以前去过的地方而无需回溯的任何通道，它将继续无限地沿着同一条路径递归。

于 2012-07-13T21:15:16.400 回答
1

您在堆栈上分配的内存不足。也就是在给定时间超出 JVM 资源的情况下，您的递归倍增太快。

您可以增加内存，然后终止此方法的所有其他迭代，或更改您的算法。更改堆栈大小将是一个糟糕的解决方案，但即使您的代码有缺陷如何在 Eclipse 中增加堆栈大小，它也可能会起作用我建议您标记您已经访问过的区域

迷宫是Cell[][] maze

  public class Cell{
    boolean visited = false;
    Wall left;
    Wall right;
    Wall up;
    Wall bottom;
    boolean end;

    //Settters and Getters
    }

每次点击时将访问变量设置为true，然后将代码更改为

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].getButton() == null)&&(maze[i][j].visited==false)){
            return solveMaze(maze,i,j+1); 
        }

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

除非您自己解决问题，否则我不会实施它可能能够重复相同问题的答案，但您可能无法使用类似策略对类似问题提出新的答案。

于 2012-07-13T21:17:04.613 回答
1

首先，您向下走，直到到达一堵墙。然后，一个向上 - 然后再次向下。一个向上，一个向下 - 直到 java 检测到这很愚蠢并以 StackOverFlowError 停止；）

于 2012-07-13T21:18:57.133 回答