Java解决递归问题的迷宫

Question

我有一个任务，我应该能够显示从入口到出口的迷宫路径，我已经得到它的工作程度，但当迷宫得到更多复杂的死胡同，这样的程序进入无限递归。如果你能给我任何帮助，让我指向正确的方向，那将是非常感谢。

穆现行理论可以在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);  
    } 
} 

Answer 1

其他人已经描述了适当的方法来解决这个问题，但我认为这是值得指出的为什么你的程序不会扩展到更复杂的迷宫。

由于duffymo暗示，问题在于你的算法不能正确地进行任何回溯 - 当一个分支变成死胡同，然后返回到前一个方格时，它不记得这个所有。并且由于它以固定顺序尝试退出，所以总是立即尝试退出失败退出。

看看solveRecursively函数是如何定义的，你会发现在任何给定的房间里，只有一个方向会被尝试。如果一个房间有一个向东的出口，那么它是否有任何其他出口，因为if-else块从不考虑它们。

因此，事实证明，您的解决逻辑将失败（即进入两个房间之间的无限循环）任意如果正确的解决方案不是您按照您的顺序从每个房间的“第一”出口在那里定义了。

（A速战速决将存储对每个房间/方向一个简单的布尔标志。你叫递归调用之前，如果你在那个房间里最终回到重新设置它，那么，你知道是方向没有按” t可以让if区块通过尝试其他出口，重构这个以使用典型的BFS逻辑，就像Nikita所说的那样，总体上会更好）

Answer 2

我敢打赌，你需要某种树来跟踪你去过的地方。

递归失败时，通常意味着编写该方法的人没有正确表达停止条件。你的是啥呢？

我认为这是我在电脑上遇到过的第一场比赛。这是我获得本科学位的学校的IBM大型机。 I/O使用纸质电传。玩这款迷宫游戏时，许多盐眼泪都被冲走了。非常有趣。

Answer 3

你只需要保留二维数组的值，该值指示该单元格是否被访问过：你不想两次通过同一个单元格。

除此之外，它只是广度优先搜索（深度优先搜索也很好，如果你不想要最短路径）。

一些链接
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]; 
} 

编辑
上面的代码是二维迷宫，我刚才注意到您有立体版本。但在上面的例子中很容易引入第三个坐标。
让我知道是否有任何困难。

Answer 4

解开迷宫时，将其表示为6元图形，其中每个节点是一个房间，每条边代表六个方向之一的行程。然后，您可以应用一些众所周知的算法来寻找最短路径。

This page描述了用于通过如此构造的图寻找路径的各种解决方案。您的图形比描述真实世界地图的图形更容易，因为沿着任何边缘行驶的成本等于沿着任何其他边缘行驶的成本。

请特别注意Dijkstra's algorithm。