Java用递归问题解决迷宫-Java 学习之路

我有一个任务，我应该能够显示从入口到出口的迷宫的路径，我已经让它工作到一定程度，但当迷宫变得更加复杂的死胡同，这样的程序进入无限递归 . 如果你能给我任何帮助，指出我正确的方向，我将不胜感激 .

Mu当前的理论可以在Room类中找到 .

这里是Room类，其中存储了连接迷宫的每个房间的引用，有点像链接列表，链接在6个方向，北，南，东，西，上和下 .

import java.util.ArrayList;

public class OurRoom
{
    private OurRoom exits[];
    private String name;
    private static ArrayList<OurRoom> list;

    public OurRoom()
    {
        this(null);
    }

    public OurRoom(String name)
    {
        this.name = name;
        this.list = new ArrayList<OurRoom>();
        exits = new OurRoom[Direction.values().length];
        for(OurRoom exit : exits)
        {
            exit = null;
        }
    }       


    public void connectTo(OurRoom theOtherRoom, Direction direction)
    {
        exits[direction.ordinal()] = theOtherRoom;
        theOtherRoom.exits[direction.getOpposite().ordinal()] = this;
    }

    public OurRoom getExit(Direction direction)
    {
        return exits[direction.ordinal()];
    }

    public boolean lookExit(Direction direction)
    {
        return exits[direction.ordinal()] != null;
    }

    public String getName() {
        return name;
    }

    public OurRoom solveRecursively(OurRoom exit) {
        list.add(this);
        if(this == exit) {
            return this;
        }else { 
            OurRoom temp = null;            
            if(lookExit(Direction.east)) {
                temp = exits[Direction.east.ordinal()].solveRecursively(exit);              
            }   
            else if(lookExit(Direction.up)) {
                temp = exits[Direction.up.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.south)) {
                temp = exits[Direction.south.ordinal()].solveRecursively(exit);             
            }           
            else if(lookExit(Direction.down)) {
                temp = exits[Direction.down.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.west)) {
                temp = exits[Direction.west.ordinal()].solveRecursively(exit);      
            }   
            else if(lookExit(Direction.north)) {
                temp = exits[Direction.north.ordinal()].solveRecursively(exit); 
            }
            return temp;
        }
    }

    public ArrayList<OurRoom> getList() {
        return list;
    }

}

这是方向枚举

public enum Direction
{
    north, south, east, west, up, down;

    public Direction getOpposite()
    {
        switch(this)
        {
            case north:
                return south;
            case south:
                return north;
            case east:
                return west;
            case west:
                return east;
            case up:
                return down;
            case down:
                return up;
            default:
                return this;
        }
    }
}

以下是迷宫如何构建的示例 .

import java.util.ArrayList;
import java.util.Iterator;

public class OurMaze
{
    private OurRoom entrance, exit;

    public OurMaze()
    {
        this(1);
    }

    public OurMaze(int mazeNumber)
    {
        entrance = null;
        exit = null;
        switch(mazeNumber)
        {
        case 0:
            break;
        case 1:
            this.buildMaze1();
            break;             
        default:
        }
    }

    public OurRoom getEntrance()
    {
        return entrance;
    }

    public OurRoom getExit()
    {
        return exit;
    }

    public Iterator<OurRoom> findPathRecursively() {
        entrance.solveRecursively(exit);
        ArrayList<OurRoom> list = entrance.getList();       
        return list.iterator();
    }

    private void buildMaze1()
    {
        OurRoom room1, room2;

        room1 = new OurRoom("Room 1");
        room2 = new OurRoom("Room 2");
        room1.connectTo(room2, Direction.north);

        entrance = room1;
        exit = room2;
    }

    public static void main(String[] args) {
        OurMaze maze = new OurMaze(1);      
    }
}

4 回答

1

其他人已经描述了解决这个问题的适当方法，但我认为值得指出为什么你的程序不能扩展到更复杂的迷宫 .

正如duffymo暗示的那样，问题在于你的算法根本没有记住这一点 . 并且由于它以固定顺序尝试退出，因此它将始终重试失败的退出 .

看看 solveRecursively 函数是如何定义的，如果它有任何其他出口，你甚至可以解决这个问题，因为if-else块会考虑它们 . {2458496_

事实证明，在任何情况下，你的解决逻辑都会失败（即在两个房间之间进入无限循环），在那里没有正确的解决方案 .

（快速解决方法是在每个房间/方向上存储一个简单的布尔标志 . 在你调用递归调用之前设置它，然后如果你再次回到那个房间，你知道方向不能解决并且可以让if块会通过尝试其他出口之一 . 重构这个以使用典型的BFS逻辑，正如Nikita所建议的那样，总体上会更好）

回复于 2024-04-29T11:13:38+08:00
6
您只需要保留二维数组，其值指示是否访问过该单元格：您不希望两次通过同一单元格 .

除此之外，它只是广度优先搜索（深度优先搜索也很好，如果你不想要最短的路径） .

一些链接
http://en.wikipedia.org/wiki/Flood_fill
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

样本搜索例程 .
```
void dfs(int i, int j) {
        if cell(i, j) is outside of maze or blocked {
            return
        }
        if visited[i][j] {
            return
        }
        visited[i][j] = true;
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
```
如果与 visited 一样，对于每个单元格，您可以找到路径本身，以保留您来自它的单元格 . 因此，打印看起来像这样（只是一个伪代码） .
```
var end = exit_point;
while (end != start_point) {
   print end;
   end = came_from[end];
}
```
edit
上面的代码是针对二维迷宫的，我只是注意到你有三维版本 . 但是在上面的例子中引入第三个坐标很容易 .
如果有任何困难，请告诉我 .
回复于 2024-04-29T11:13:38+08:00
1

我敢打赌你需要一棵树来跟踪你去过的地方 .

当递归失败时，通常意味着编写该方法的人没有正确地表达停止条件 . 你的是啥呢？

我认为这是我在电脑上遇到过的第一款游戏 . 这是我获得本科学位的学校的IBM大型机 . I / O是纸质电传打字机 . 许多盐的眼泪都在玩这个迷宫游戏时被冲走的账户美元 . 非常有趣 .

回复于 2024-04-29T11:13:38+08:00
2

在解决迷宫时，将其表示为6-ary图，其中每个节点都是一个房间，每个边代表六个方向之一的行程 . 然后，您可以应用一些众所周知的算法来查找最短路径 .

This page描述了用于通过如此构造的图来寻找路径的各种解决方案 . 您的图表比描述真实世界 Map 的图表更容易，因为沿着任何边缘行进的成本等于沿着任何其他边缘行进的成本 .

特别要确保看看Dijkstra's algorithm .

回复于 2024-04-29T11:13:38+08:00

Java用递归问题解决迷宫

4 回答

相关问题