迷路のバックトラッキングアルゴリズムの解決の問題訪問された部屋の設定でのアルゴリズム
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;
}
}
これが私のメインクラスのパブリッククラスメインです{
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」部屋に1回だけ移動し、そこで無限にループするだけで、スタックは部屋「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());
}
}
解決
これを行う方法はいくつかあります。
1つは、追跡とバックトラッキングが進むにつれて設定/設定/設定した各部屋のオブジェクトに「IsVisited」ブールフラグを保持することです。これは、迷路のみを単一のスレッド検索で検索できることを意味します（これは重要かもしれません）。
もう1つは、あなたが比較する訪問された部屋のリストを保持することです（ここでは、新しい部屋をリストに「プッシュ」するだけで、コールスタックを使用してこれをパスすると自動的にポップすることが比較的簡単である必要があります。リスト）。
また、検索ごとのハッシュテーブルを使用することもできます。これにより、リストを検索するよりも（おそらく）より速いルックアップが可能になり、マルチスレッドが可能になります（「複数のスレッドが迷路を検索できます」、 1つのスレッドが同じ検索に参加できる "）。
おそらく私が考えていないこともいくつかありますが、これらの3つはすべて、実装するためにかなり簡単にする必要があります。
他のヒント
迅速で非常に最適化されていないアプローチ：
訪問した各部屋については、保管してください 可能 道順（make an enum Direction そしてa Set<Direction> たとえば、前の部屋から取った方向から来たものを削除します。したがって、A4からB4に移動すると、A4からB4から西から東を除去します。後ろに追跡する必要がある場合は、訪問されていない方向のある部屋を見つけるまでスタックを解き放ちます（可能な方向のリストは空ではありません）。次の部屋を試してください。この時点でスタックが空になった場合、ターゲットルームを見つけずにすべての可能性を試しました。
私が言ったように、これは非常に最適化されていませんが、機能するはずです。
いくつかのコメント：
あなたのコードには、使用しているいくつかの機能がありません。迷路クラスにはgetPaths（）メソッドはありません。オンラインでコードを投稿する場合は、簡単に編集できるようにしてください。あなたの場合、私は推測する必要があります。GetPaths（）は、探索する可能性のあるパスを保存しようとするある種のスタックを返しますが、実際に何をするかを確かめる方法はありません。
また、投稿する前にコードを簡素化してみてください。あなたの迷路はかなり複雑であり、あなたの構築された迷路が写真のものと一致するかどうかを確認するためにそれを描く必要があります。はるかにシンプルな迷路で問題を再現できる場合は試してください（たぶん2つまたは3つの部屋）。また、単純化すると、問題がどこにあるかについての多くのヒントが得られます。単純化している間、問題が突然消えるポイントがあります。これは、実際のバグについて多くのことを教えてくれます。
コードの何が問題なのかについてのいくつかのアイデア：各方向に、その方向にある方向にスーグロームを設定します。 Soughtroomは現在検索している部屋であると仮定しています。その後、その部屋をスタックに押し込みます。ただし、バックトラッキングの場合、各ブランチに以前の状態に戻るすべての情報を保存する必要があります。最初に現在の部屋を設定してから押した場合、前の状態からの情報が失われます。逆に試してみて、何が起こるかを確認してください。
