1
누군가가 내 방 검색 알고리즘으로 나를 도울 수 있는지 찾는다.
미로 해결을 위해 백 트랙킹 알고리즘을 구현하려고합니다. 나는 내가 이미 방문한 방을 암기해야만하는 곳에 머물러있다.
미로는 객실에서 구성되며 각 방에는 북쪽, 동쪽, 남쪽 및 서쪽의 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();
}
}
은 미로는 다음과 같습니다 : 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======");
}
}
입니다 http://i.stack.imgur.com/2KePs.jpg 문제는 내 findPathTo(roomName) 방법입니다, 어떤 f 방으로 향하는 경로. 방 D4에 들어가면 알고리즘이 "A4"에서 "B4"방으로 동쪽으로 한 번 이동하고 거기에서 무한 루프가되고 스택이 방 "B4"만으로 커집니다. 왜 그것은 예를 들어 다음 방 "B3"또는 "C4"로 이동하지 않습니까?
편집 : 각 방문 방에 들어
의 수 방향 (AN enum Direction을 저장하고 Set<Direction>에 대한 : 여기에 작업 코드
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());
}
}
방을 방문 할 때 참으로 설정 한 "방문한"부울 플래그를 추가하십시오. 역 추적 중 아직 시도하지 않은 방을 통해서만 이동합니다. –
안녕하세요, 감사합니다. 나는 그것을했고 그것은 달성하기위한 가장 쉬운 방법이었다. – Skyzer