java - 设置访问房间的迷宫解决回溯算法的问题

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

迷宫看起来像这样:http://i.stack.imgur.com/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 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” boolean 标志，作为您的跟踪和回溯 yield 。这意味着您只能单线程搜索您的迷宫(这可能重要也可能无关紧要)。

另一种方法是保留一个已访问过的房间的列表，并与之进行比较(这里的优点是，如果您使用调用堆栈，只需将一个新房间“推送”到列表中并让它自动弹出应该相对容易通过此列表)。

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

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