Проблема с решающим алгоритмом обратного отслеживания лабиринта
https://stackoverflow.com/questions/5379115
-
28-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я стремлюсь, если кто -то сможет помочь мне в моей комнате, искать алгоритм
Я пытаюсь реализовать алгоритм возврата для решения лабиринта. Я застрял в том месте, где я должен запомнить комнаты, которые я уже посетил.
Лабиринт состоит из комнат, а в каждой комнате есть 4 стороны - север, восток, юг и запад. Каждая комната связана с следующей комнатой, сделав дверь к желаемой стороне, т.е. room1.createNorth(roomName) Что создает новую комнату на севере, и в новой комнате есть южная дверь, чтобы связаться с первой, как вы можете увидеть в классе моей комнаты.
Вот мой нарезанный класс комнаты, который представляет каждую комнату в лабиринте. Я снял юг, запад и восток, которые идентичны моим методам, которые имеют дело с северной стороной.
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;
}
}
Вот мой основной класс открытого класса 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, то мой алгоритм перемещается только один раз на восток в комнату «B4» от «A4», и там он просто бесконечно зацикливается, а стек просто растет с комнатой «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());
}
}
Решение
Есть несколько способов сделать это.
Можно было бы сохранить «IseSited» логический флаг в каждом объекте комнаты, который вы устанавливаете/не определяете поступление отслеживания и отслеживания. Это означает, что вы можете только однопоточный просмотр вашего лабиринта (это может иметь или не иметь значения).
Другим было бы соблюдать список посещаемых комнат, с которыми вы сравниваете (преимущество здесь заключается в том, что должно быть относительно легко просто «выдвигать» новую комнату в список и автоматически выскочить, если вы используете стек для вызовов, чтобы передать это список).
Вы также можете использовать хэштату для поиска места для Isvisible, это позволяет (возможно) более быстрые поиски, чем поиск списка, позволяет провести многопоточное (как в «более одного потока может искать лабиринт», а не «больше чем один поток может участвовать в одном поиске »).
Вероятно, есть несколько вещей, о которых я не думал, но все три из них должны быть довольно простыми для реализации.
Другие советы
Быстрый и очень неоптимизированный подход:
Для каждой посещаемой комнаты храните возможный направления (сделайте enum Direction и Set<Direction> Например) и удалите тот, из которого вы пришли, а также направление, которое вы выбрали из предыдущей комнаты. Таким образом, переходя от A4 к B4, вы удалите на восток от A4 и запад от B4. Если вам нужно отследить, просто расслабьтесь в стеке, пока не найдете комнату с неофициальным направлением (список возможных направлений не пуст) и попробуйте следующий. Если на этом этапе стек становится пустым, вы попробовали все возможности, не найдя целевую комнату.
Как я уже сказал, это очень неоптимизировано, но это должно работать.
Некоторые комментарии:
В вашем коде не хватает некоторых функций, которые вы используете. В вашем классе лабиринта нет метода getPaths (). Если вы публикуете код в Интернете, постарайтесь убедиться, что он легко компилируется и тестируется. В вашем случае я должен был бы угадать, что getPaths () возвращает какой -то стек, на котором вы пытаетесь сохранить возможные пути, которые будут изучены, но нет никакого способа быть уверенным, что на самом деле это делает.
Также попробуйте упростить код перед публикацией. Ваш лабиринт довольно сложный, и нужно было бы нарисовать его, чтобы увидеть, соответствует ли ваш построенный лабиринт тот, который на картинке. Попробуйте, если вы можете воспроизвести проблему с гораздо более простым лабиринтом (может быть, 2 или 3 комнаты). Также упрощение часто дает вам много намеков относительно того, где может быть проблема. В то время как вы упрощаетесь, будет момент, когда проблема внезапно исчезнет. Это многое говорит вам о реальной ошибке.
Некоторые идеи о том, что может быть не так с вашим кодом: в каждом направлении вы устанавливаете Soughtroom в тот, который в этом направлении. Я предполагаю, что Soughtroom - это комната, в которой находится ваш поиск в настоящее время. Затем вы толкаете эту комнату на стек. Однако для возврата вам необходимо хранить в каждой филиале всю информацию, которая возвращает вас к предыдущему штату. Если вы сначала установите текущую комнату, а затем нажмите ее, информация из предыдущего состояния потеряна. Попробуйте наоборот и посмотрите, что произойдет.
