Java解决递归问题的迷宫
我有一个任务,我应该能够显示从入口到出口的迷宫路径,我已经得到它的工作程度,但当迷宫得到更多复杂的死胡同,这样的程序进入无限递归。如果你能给我任何帮助,让我指向正确的方向,那将是非常感谢。Java解决递归问题的迷宫
穆现行理论可以在Room类中找到。
这里是房间类,其中存储了连接迷宫的每个房间的参考,有点像链接在6个方向上,北,南,东,西,向上和向下的链接列表。
import java.util.ArrayList;
public class OurRoom
{
private OurRoom exits[];
private String name;
private static ArrayList<OurRoom> list;
public OurRoom()
{
this(null);
}
public OurRoom(String name)
{
this.name = name;
this.list = new ArrayList<OurRoom>();
exits = new OurRoom[Direction.values().length];
for(OurRoom exit : exits)
{
exit = null;
}
}
public void connectTo(OurRoom theOtherRoom, Direction direction)
{
exits[direction.ordinal()] = theOtherRoom;
theOtherRoom.exits[direction.getOpposite().ordinal()] = this;
}
public OurRoom getExit(Direction direction)
{
return exits[direction.ordinal()];
}
public boolean lookExit(Direction direction)
{
return exits[direction.ordinal()] != null;
}
public String getName() {
return name;
}
public OurRoom solveRecursively(OurRoom exit) {
list.add(this);
if(this == exit) {
return this;
}else {
OurRoom temp = null;
if(lookExit(Direction.east)) {
temp = exits[Direction.east.ordinal()].solveRecursively(exit);
}
else if(lookExit(Direction.up)) {
temp = exits[Direction.up.ordinal()].solveRecursively(exit);
}
else if(lookExit(Direction.south)) {
temp = exits[Direction.south.ordinal()].solveRecursively(exit);
}
else if(lookExit(Direction.down)) {
temp = exits[Direction.down.ordinal()].solveRecursively(exit);
}
else if(lookExit(Direction.west)) {
temp = exits[Direction.west.ordinal()].solveRecursively(exit);
}
else if(lookExit(Direction.north)) {
temp = exits[Direction.north.ordinal()].solveRecursively(exit);
}
return temp;
}
}
public ArrayList<OurRoom> getList() {
return list;
}
}
这里是方向枚举
public enum Direction
{
north, south, east, west, up, down;
public Direction getOpposite()
{
switch(this)
{
case north:
return south;
case south:
return north;
case east:
return west;
case west:
return east;
case up:
return down;
case down:
return up;
default:
return this;
}
}
}
这里是迷宫的是如何建立一个例子。
import java.util.ArrayList;
import java.util.Iterator;
public class OurMaze
{
private OurRoom entrance, exit;
public OurMaze()
{
this(1);
}
public OurMaze(int mazeNumber)
{
entrance = null;
exit = null;
switch(mazeNumber)
{
case 0:
break;
case 1:
this.buildMaze1();
break;
default:
}
}
public OurRoom getEntrance()
{
return entrance;
}
public OurRoom getExit()
{
return exit;
}
public Iterator<OurRoom> findPathRecursively() {
entrance.solveRecursively(exit);
ArrayList<OurRoom> list = entrance.getList();
return list.iterator();
}
private void buildMaze1()
{
OurRoom room1, room2;
room1 = new OurRoom("Room 1");
room2 = new OurRoom("Room 2");
room1.connectTo(room2, Direction.north);
entrance = room1;
exit = room2;
}
public static void main(String[] args) {
OurMaze maze = new OurMaze(1);
}
}
其他人已经描述了适当的方法来解决这个问题,但我认为这是值得指出的为什么你的程序不会扩展到更复杂的迷宫。
由于duffymo暗示,问题在于你的算法不能正确地进行任何回溯 - 当一个分支变成死胡同,然后返回到前一个方格时,它不记得这个所有。并且由于它以固定顺序尝试退出,所以总是立即尝试退出失败退出。
看看solveRecursively
函数是如何定义的,你会发现在任何给定的房间里,只有一个方向会被尝试。如果一个房间有一个向东的出口,那么它是否有任何其他出口,因为if-else块从不考虑它们。
因此,事实证明,您的解决逻辑将失败(即进入两个房间之间的无限循环)任意如果正确的解决方案不是您按照您的顺序从每个房间的“第一”出口在那里定义了。
(A速战速决将存储对每个房间/方向一个简单的布尔标志。你叫递归调用之前,如果你在那个房间里最终回到重新设置它,那么,你知道是方向没有按” t可以让if区块通过尝试其他出口,重构这个以使用典型的BFS逻辑,就像Nikita所说的那样,总体上会更好)
我敢打赌,你需要某种树来跟踪你去过的地方。
递归失败时,通常意味着编写该方法的人没有正确表达停止条件。你的是啥呢?
我认为这是我在电脑上遇到过的第一场比赛。这是我获得本科学位的学校的IBM大型机。 I/O使用纸质电传。玩这款迷宫游戏时,许多盐眼泪都被冲走了。非常有趣。
你只需要保留二维数组的值,该值指示该单元格是否被访问过:你不想两次通过同一个单元格。
除此之外,它只是广度优先搜索(深度优先搜索也很好,如果你不想要最短路径)。
一些链接
http://en.wikipedia.org/wiki/Flood_fill
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search
示例搜索程序。
void dfs(int i, int j) {
if cell(i, j) is outside of maze or blocked {
return
}
if visited[i][j] {
return
}
visited[i][j] = true;
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);
}
路径本身的话可以发现,像visited
,每个单元格你保持距离,你来到它的细胞。所以,打印会看起来像这样(只是一个伪代码)。
var end = exit_point;
while (end != start_point) {
print end;
end = came_from[end];
}
编辑
上面的代码是二维迷宫,我刚才注意到您有立体版本。但在上面的例子中很容易引入第三个坐标。
让我知道是否有任何困难。
解开迷宫时,将其表示为6元图形,其中每个节点是一个房间,每条边代表六个方向之一的行程。然后,您可以应用一些众所周知的算法来寻找最短路径。
This page描述了用于通过如此构造的图寻找路径的各种解决方案。您的图形比描述真实世界地图的图形更容易,因为沿着任何边缘行驶的成本等于沿着任何其他边缘行驶的成本。
请特别注意Dijkstra's algorithm。
Dijkstra在这里太重了,旧的bfs会解决这个问题更简单:) – 2010-07-12 00:18:00
我想你是对的。阿斯克尔只给出了一个两室迷宫作为例子,所以我不知道他的迷宫有多复杂。 – 2010-07-12 00:33:29
感谢您为我写出来,我只是拿出所有其他语句,然后检查,看看我的数组列表是否包含节点,因为我保留了我已经访问过的所有节点。现在就像魅力一样。 :) – 2010-07-12 04:07:41