6

所以我正在尝试创建一个迷宫求解程序来解决 X 和 O 的迷宫。我想做的是创建一个点类,这样我就可以创建一个二维点数组,这将允许打印到输出页面以及实现堆栈相对简单。

我想在实际程序本身中实现的一般思想的最简单算法我认为应该是:

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

但是我无法提出更深入的算法,也无法确定我的 Points 课程。我知道对于点我应该设置 X 坐标,并设置 Y 坐标以及两者的吸气剂。你认为我需要比这两个更多的方法吗?就像,我是否应该创建一个传递 x 坐标和 y 坐标作为参数的方法,这样我就可以将它们作为一个整体推在一起,而不是单独设置 x 和 y?

这是一个示例迷宫的样子,您从右下角开始并尝试遍历左上角,其中 X 为墙壁,O 为迷宫中的开放空间:

O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O 
X X O X X X O
4

7 回答 7

1

你确定你的算法能解决任何迷宫吗?我认为它会卡在这个简单的模型中(其中 S 是开始,F 是结束):

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

你的算法会沿着第一个走廊向下走,直到它面对秋天,左转,面对“北”墙,再次左转,然后走回第一个走廊,在那里它会再次左转两次,并不断重复这个问题。

右手规则算法(参见维基百科页面,以及更多迷宫算法的其他部分)应该可以解决任何没有循环的迷宫,并且应该很容易在 java 中实现。

于 2012-02-08T15:51:34.013 回答
0

使用墙跟随算法:http ://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

于 2012-02-08T17:00:03.590 回答
0

你可以使用一个

Stack<Point> points = new Stack<>();

// add a point
Point p = new Point(x, y);
if (points.contains(p))
   // been here before, in circles.
else
   points.add(p);
于 2012-02-08T15:48:27.327 回答
0

对于算法,您可以使用回溯EDIT虽然它与您的一般想法不太匹配。)您只需要意识到您的动作被“推送”到虚拟堆栈中,并且它们必须被取消推送(因此撤消。)您可能如果“机器人”是一个实际移动的物体,则必须自己实现堆栈,但如果您只想解决迷宫,则可以依赖调用堆栈。

于 2012-02-08T15:52:19.527 回答
0

对于算法部分,通过堆栈的深度优先递归是优选的。类似于以下内容:

currentSpot = (0,0)  // The starting point //

while(! currentSpot.isExit()) {

  if (! currentSpot.left().isWall()) stack.push(currentSpot.left());
  if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward());
  if (! currentSpot.right().isWall()) stack.push(currentSpot.right());

  currentSpot = stack.pop();  // Get the next location //
}

您将希望您的点类返回每个给定方向上的下一个点(向后除外),并检测您何时处于迷宫边缘。您可能需要一个包含所有点、打印、存储 X/O 等的 Maze 类。因此,您可以将初始 currentSpot = (0,0) 替换为 currentSpot = Maze.getStartingSpot() ;

于 2012-02-08T15:53:07.030 回答
0

对于您的算法,您不需要堆栈。只有当您使用回溯来撤消遍历决策时,您才需要一个堆栈。

于 2012-02-08T15:54:12.397 回答
0

我在学校的时候曾经解决过这个问题,我们使用了类似于左右手规则的解决方案。我相信我们是在学习链接列表时做到了这一点。简而言之,算法是这样的:

  1. 向左走。如果可能,请重复。
  2. 如果没有,直接走。如果可能,请返回步骤 1。
  3. 如果没有,请向右走。如果可能,请返回步骤 1。

在每一步,您还要检查您所站的位置是否是终点。如果您无法继续(即无法向左、直或向右),则将您所在的位置标记为“已访问”并后退。冲洗并重复。

于 2012-02-08T18:54:50.043 回答