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セルの一部にno がない場合は 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

ソルバーメソッドで円を描いているように思えます。Breadth-First Search
に 慣れることをお勧めします。これは、あまり大きくない状態検索の問題によく使用されます。

迷路を検索する方法についてのヒューリスティックな「知識」がある場合は、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

まず、壁に到達するまで下ります。次に、1 つ上げてから、もう一度下げます。そして、1 つ上、1 つ下 - Java がこれがかなりばかげていることを検出し、StackOverFlowError で停止するまで ;)

于 2012-07-13T21:18:57.133 に答える