设置访问过的房间的迷宫求解回溯算法的问题

Question

我寻求是否有人可以帮助我解决我的房间搜索算法
我正在尝试实现一种回溯算法来解决迷宫。我被困在我应该记住我已经访问过的房间的地方。
迷宫由房间组成，每个房间有 4 个面 - 北、东、南、西。每个房间都通过在所需一侧制作一扇门来链接到下一个房间，即 room1.createNorth(roomName) ，它会在北面创建一个新房间，而新房间有南门来链接回第一个房间，如下所示你可以在我的 Room 课程中看到。

这是我的切碎的房间类，它代表迷宫中的每个房间。我删除了南、西、东方向，这与我处理北侧的方法相同。

public class Room {

    private String name;
    private Room north;
    private Room east;
    private Room west;
    private Room south;
    private boolean isExit = false;
    private Maze maze;

    /**
     * @return name room
     */
    public String getName() {
        return this.name;
    }

    /**
     * Sets room name
     * 
     * @param name
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * Gets northern room if any
     * 
     * @return pointer to northern room if any, otherwise <code>null</code>
     */
    public Room getNorth() {
        return this.north;
    }

    /**
     * Sets the door to the next room to the north in that room and in the other
     * room sets southern door as connecting back to that room
     * 
     * @param otherRoom
     */
    public void setNorth(Room otherRoom) {
        this.north = otherRoom;
        otherRoom.south = this;
    }

    /**
     * creates a new room to the north and connects back to this room
     * 
     * @param name
     *            of the room
     * @return created room
     */
    public Room createNorth(String name) {
        Room otherRoom = null;

        // create new room in that direction ONLY if there is no room yet
        if (this.getNorth() == null) { // get northern direction, if it's null,
                                        // then it's okay to create there
            otherRoom = new Room(); // create!
            this.setNorth(otherRoom); // set the door
            otherRoom.setName(name); // set the name

        } else { // there is a room in that direction, so don't create a new
                    // room and drop a warning
            System.out.println("There is already a room in northern direction");
        }

        return otherRoom;
    }

    /**
     * Asdf
     * 
     * @return maze
     */
    public Maze getMaze() {
        return this.maze;
    }

    /**
     * Set maze
     * 
     * @param maze
     */
    public void setMaze(Maze maze) {
        this.maze = maze;
    }

    /**
     * @param roomName path to this room must be found
     */
    public void findPathTo(String roomName) {
        Room soughtRoom = this.getMaze().getEntry();

        while (!(soughtRoom.getName().equalsIgnoreCase(roomName))) {

//          here should be also a method such as setRoomAsVisited()

            if (this.getWest() != null) {
                soughtRoom = this.getWest();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else if (this.getNorth() != null) {
                soughtRoom = this.getNorth();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else if (this.getEast() != null) {
                soughtRoom = this.getEast();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else if (this.getSouth() != null) {
                soughtRoom = this.getSouth();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else {
                if (this.getMaze().getPaths().isEmpty()) {
                    break; // no more path for backtracking, exit (no solution found)
                }
                // dead end, go back!
                soughtRoom = this.getMaze().getPaths().pop();
            }
            System.out.println(this.getMaze().getPaths().toString());
        }


    }

    @Override
    public String toString() {
        return "Room name is " + this.getName();
    }
}

迷宫看起来像这样： https://i.sstatic.net/2KePs.jpg 其中 S 是起点

我的迷宫课程

public class Maze {

    Room room;

/**
 * helper collection path stack for findPathTo() method
 */
private Stack<Room> paths = new Stack<Room>();

/**
 * @return path for exit
 */
public Stack<Room> getPaths() {
    return this.paths;
}

    /**
     * Singleton method for first room in the maze which is entry room
     * 
     * @return room if no room is created then creates new, otherwise returns
     *         already created room
     */
    public Room getEntry() {
        if (this.room == null) {
            this.room = new Room();
            return this.room;
        }
        return this.room;
    }
}

这是我的主课程 public class Main {

    public static void main(String[] args) {

        Maze maze = new Maze();
        maze.getEntry().setName("A4"); // set first room's name A4
        // labyrinth creation
        maze.getEntry().createEast("B4").createNorth("B3").createWest("A3");
        maze.getEntry().getEast().getNorth().createNorth("B2").createWest("A2")
                .createNorth("A1");
        maze.getEntry().getEast().getNorth().getNorth().createNorth("B1");
        maze.getEntry().getEast().getNorth().getNorth().createEast("C2")
                .createNorth("C1").createEast("D1");
        maze.getEntry().getEast().createEast("C4").createEast("D4");
        maze.getEntry().getEast().getEast().createNorth("C3").createEast("D3")
                .createNorth("D2").setExit(true);

        System.out.println("=====Test findPathTo method======");
        maze.getEntry().setMaze(maze); // set maze instance to our entrance room
        maze.getEntry().findPathTo("B4");

        System.out.println("=====End of testing findPathTo method======");

    }

}

问题出在我的 findPathTo(roomName) 方法中，该方法查找到房间的路线。 如果我进入房间 D4，那么我的算法仅从“A4”向东移动到“B4”房间一次，并且在那里无限循环，并且堆栈仅随着房间“B4”而增长。为什么它不向前移动，例如移动到下一个房间“B3”或“C4”？

编辑：这是工作代码

public void findPathTo(String roomName) {

        Room soughtRoom = this.getMaze().getEntry();

        while (!(soughtRoom.getName().equalsIgnoreCase(roomName))) {

            if (soughtRoom.getWest() != null && soughtRoom.getWest().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getWest();
                soughtRoom.isVisited = true;

            }
            else if (soughtRoom.getNorth() != null && soughtRoom.getNorth().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getNorth();
                soughtRoom.isVisited = true;

            }
            else if (soughtRoom.getEast() != null && soughtRoom.getEast().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getEast();
                soughtRoom.isVisited = true;

            }
            else if (soughtRoom.getSouth() != null && soughtRoom.getSouth().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getSouth();
                soughtRoom.isVisited = true;

            }
            else {
                if (this.getMaze().getPaths().isEmpty()) {
                    System.out.println("No solutions found :(");
                    break; // no more path for backtracking, exit (no solution found)
                }
                // dead end, go back!
                soughtRoom = this.getMaze().getPaths().pop();
            }
            System.out.println("Path rooms: " + this.getMaze().getPaths().toString());
        }
    }

Answer 1

有几种方法可以做到这一点。

一种方法是在跟踪和回溯过程中设置/取消设置的每个房间对象中保留“isVisited”布尔标志。这意味着您只能单线程搜索您的迷宫（这可能重要也可能不重要）。

另一种方法是保留您比较的已访问房间的列表（这里的优点是，如果您使用调用堆栈传递此信息，则将新房间“推”到列表中并自动弹出它应该相对容易）列表）。

您还可以使用 isVisible 的每个搜索空间哈希表，这允许（可能）比搜索列表更快的查找，允许多线程（如“多个线程可以搜索迷宫”，而不是“更多”）一个线程可以参与同一搜索”）。

可能还有一些我没有想到的事情，但是所有这三件事都应该非常容易实现。

Answer 2

一种快速且高度未优化的方法：

对于每个访问过的房间，存储可能的方向（例如，创建枚举方向和设置 ）并删除您来自的房间以及您从前一个房间走的方向。因此，从 A4 移动到 B4，您需要从 A4 中删除 EAST，从 B4 中删除 WEST。如果您必须回溯，只需展开堆栈，直到找到一个具有未访问方向的房间（可能的方向列表不为空），然后尝试下一个方向。如果此时堆栈变空，则说明您尝试了所有可能性，但没有找到目标房间。

正如我所说，这是高度未优化的，但它应该有效。

Answer 3

一些评论：

您的代码缺少您正在使用的一些功能。您的迷宫类中没有 getPaths() 方法。如果您在线发布代码，请尝试确保它易于编译和测试。在你的情况下，我不得不猜测， getPaths() 返回某种堆栈，你尝试在其中存储要探索的可能路径，但无法确定它实际上做了什么。

在发布之前也尝试简化代码。你的迷宫相当复杂，需要把它画出来，看看你搭建的迷宫是否与图片上的相符。尝试一下是否可以用更简单的迷宫（可能有 2 个或 3 个房间）重现该问题。此外，简化通常会给你很多关于问题可能出在哪里的提示。当你进行简化时，总会有一个问题会突然消失的时刻。这告诉您很多有关实际错误的信息。

关于您的代码可能存在问题的一些想法：
在每个方向，您将 SeedRoom 设置为该方向的那个。我假设 SeedRoom 是您当前搜索的房间。然后你将该房间压入堆栈。然而，对于回溯，您需要在每个分支存储使您返回到先前状态的所有信息。如果您先设置当前房间然后推送它，则先前状态的信息将丢失。反过来尝试一下，看看会发生什么。