二维迷宫求解器递归函数

Question

我正在尝试将二维矩阵实现为迷宫。有一个起点，一个终点（随机选择）。为了让它变得有点复杂，还有障碍和代理人。如果老鼠遇到障碍物，它应该原路返回并找到正确的路径。如果它遇到代理，它就会被摧毁。这是一个示例 4x4 矩阵

Key：0是障碍物，2是代理，7是起点，9是goal/ending点。 1 表示可以安全地移动到那里。

这个矩阵的正确解是：

但是老鼠并不聪明（至少对于这个程序而言），所以我正在实现一个随机移动的蛮力算法。

我尝试使用称为 mazeUtil() 的递归函数来实现它。下面是函数： maze[][] 是老鼠经过的随机初始矩阵。
solution[][] 是将跟踪移动的解决方案矩阵。
(x, y) 是网格中的当前位置 n是矩阵的大小（是方阵）

public static void mazeUtil(int maze[][], int solution[][], int x, int y, int n)
   {
      if(x == goal[0] && y == goal[1])
      {
         solution[x][y] = 1;
         return;     
      }


      int check = moveCheck(maze, x, y, n);  

//moveCheck() return 0 for Obstacle, 1 for safe path, 2 for agent, 7 for starting point (also safe path), 9 for goal (safe path)

      if (check == 2){
         solution[x][y] = 1;
         out.println("Oops! Ran into an agent!");
         return;         
      }

      else if(check == 0)
      {
         //What should I put here?
      }

      else if(check == 1 || check == 7 || check == 9)
      {
         solution[x][y] = 1;
         Random newRandom = new Random();
         int temp = newRandom.nextInt(3);

         if(temp == 0){  //move up if possible? x--
            if(x > 0)
               mazeUtil(maze, solution, x-1, y, n);
            else 
               mazeUtil(maze, solution, x+1, y, n);
         }
         else if (temp == 1){
            if (x < n-1)
               mazeUtil(maze, solution, x+1, y, n);
            else
               mazeUtil(maze, solution, x-1, y, n);
         }            
         else if(temp == 2){
            if (y < n-1)
               mazeUtil(maze, solution, x, y+1, n);
            else
               mazeUtil(maze, solution, x,y-1, n);

         }
         else if (temp == 3){
            if (y > 0)
               mazeUtil(maze, solution, x, y-1, n);
            else
               mazeUtil(maze, solution, x, y+1, n);
          }        
      }
   }

我必须随机化移动，这就是我使用随机函数的原因。如果遇到代理 (2)，我的功能会很好地工作。我还阻止了老鼠越界。通过安全路径（1）没有任何问题。但问题是当它遇到障碍时。我在考虑回溯。如何将其添加到我的函数中？比如保存最后一步，然后反过来？而且像这样的迷宫很可能没有解

往右走会撞到障碍物，往下走会撞到代理。它不能沿对角线移动。这就引出了我的第二个问题，在那种情况下我将如何终止我的递归函数。此时它唯一终止的时间是到达目标或击中代理时。

如有任何帮助，我们将不胜感激。提前致谢

Answer 1

好吧，假设我需要用与您解决问题相同的方法来解决同样的问题。（我认为最好的解决方案是路径查找，正如评论中已经提到的那样）。

我会创造

class点{ public 整数 x; public 整数 y； }

并在其中存储坐标。

我会存储老鼠在List<Point> path

在此解决方案中，您对前一点没有问题（这是列表中的最后一点）

至于算法终止——你使用带有随机数的算法。所以你不能确定你的老鼠会解决像

这样最简单的迷宫

7 1 1

1 1 1

老鼠有可能永远从(0,0)移动到(1,0)，从(1,0)移动到(0,0)。

所以，让我们再想象一下，我需要改进你的算法而不是使用好的算法。

我将存储老鼠 return 从障碍物返回或访问 path 列表中的点的次数。如果这样number > 4我会命令我的老鼠return回到原点（第7点）。并重新开始旅程。

如果老鼠需要return后退，例如10次，则算法终止。

再说一次，你的算法很搞笑，看老鼠怎么动应该很有趣，但是并没有解决问题。它不适用于大迷宫。

尝试实现寻路。如果你有问题 -- 问问题。

祝你好运！

Answer 2

如果你想随机移动，你需要知道你已经处于的状态，所以你需要一棵树，否则当老鼠处于多路位置时你可以保持最左边的路径.

现在让我们想想递归+随机。它不可能那么难。你可以有一个函数 returns 它已经在其中的点列表，并获得正确的位置作为输入，有一点问题，白痴老鼠可以回到他已经来的路，所以让通过添加前一个点作为我们函数的另一个输入来解决它。

一切就绪。现在我们想知道这只白痴老鼠是跑到死路还是跑到特工了。在这种情况下制造 2 个异常并在递归函数中处理它们如何？

嗯，我不认为路上会有更多的问题。实际上我很想自己尝试一下。那会很有趣 :D

祝白痴老鼠好运

Answer 3

在提出解决方案之前，我想对您的算法设计做一些分析。

您提到要使用随机游走算法。没问题，这是一种完全可以接受的（虽然不一定有效）寻找路径的方式。但是，您需要注意它有一些含义。

一般random walk在没有解的时候是不会告诉你的。如果你只是继续随机尝试路径，你将永远不会耗尽搜索树。
如果这是不可接受的（即它需要能够在没有解决方案时停止），那么您需要记录已经尝试过的路径并仅随机化那些尚未尝试过的路径。
除非只有一个解，否则随机游走不一定能找到最优解。换句话说，如果您的迷宫中存在环路/多条路径，则无法保证您找到最快的路径。

我实际上看不出你的问题中代理和障碍之间的区别。在这两种情况下，您都需要回溯并找到另一条路径。如果有差异，您需要指出。

因此，假设您的迷宫可能有零条或多条成功路径，并且您不是在寻找最佳路径（在这种情况下，您确实应该使用 A* 或类似路径），解决方案的结构应该类似于：

public List<Position> findPath(Set<Position> closedSet, Position from, Position to) {
    if (from.equals(to)) 
         return List.of(to);
    while (from.hasNeighboursNotIn(closedSet)) {
        Position pos = from.getRandomNeighbourNotIn(closedSet);
        closedSet.add(pos);
        List<Position> path = findPath(closedSet, pos, to);
        if (!path.isEmpty())
            return List.of(pos, path);
    }
    closedSet.add(from);
    return Collection.EMPTY_LIST;
}

这使用了大量伪代码（例如，没有 List.of(item, list)），但你明白了。

Answer 4

关于样式的快速说明，以节省以后的一些输入：maze[][]、solution[][] 和 n 都是有效的全局的，并且在递归调用之间不会改变（maze 和 solution 只是作为对相同数组的引用，并且 n 永远不会改变）。这纯粹是风格，但你可以这样写：

  private static int[][] maze;
  private static int[][] solution;
  private static int n;

  public static void mazeUtil(int x, int y) {
    ...
  }

继续您的解决方案：第一点是我不明白您是如何知道何时达到目标的；你的 mazeUtil 函数没有 return 任何东西。对于这种递归，一般方法是让求解器函数 return 一个布尔值：如果达到目标则为 true，否则为 false。一旦你得到一个 true，你只需将它一直传递回调用堆栈。每次你得到一个错误，你回溯到下一个解决方案。

所以我建议：

  public static boolean mazeUtil(int x, int y) {
    // return true if goal found, false otherwise
    ...
  }

接下来，我不确定代理和障碍之间的实际区别是什么：运行进入任何一个都会导致您回溯。所以我认为那段代码是：

  if (check == 2) {
    out.println("Oops! Ran into an agent!");
    return false;         
  }

  if (check == 0)
    out.println("Oops! Ran into an obstacle!");
    return false;         
  }

然后是递归位：这里有一点是您永远不会将失败尝试的解决方案重置为 0（实际上，因为最终算法永远不会回溯超过一个步骤，这实际上并不重要，但它很好地说明了一般方法）。鉴于我们目前所拥有的，现在应该是这样的：

  if (check == 9) {
    out.println("Found the goal!");
    return true;         
  }

  if (check == 1 || check == 7) {
    // add current position to solution
    solution[x][y] = 1;

    // generate random move within bounds
    int nextX = ...
    int nextY = ...

    if (mazeUtil(nextX, nextY)) {
      // we've found the solution, so just return up the call stack
      return true;
    }

    // this attempt failed, so reset the solution array before returning
    solution[x][y] = 0;

    return false;
  }

  // shouldn't ever get here...
  throw new IllegalStateException("moveCheck returned unexpected value: " + check);

好的，到目前为止一切顺利，但仍有问题。只要其中一个 mazeUtil 调用 return 一个值（真或假），它就会 return 一直向上调用堆栈。因此，如果您碰巧在代理人或障碍物之前找到出口，那很好，但这种可能性很小。因此，在递归时，您需要尝试所有可能的动作，而不是尝试单个动作。

有一个支撑 class 点，包含一个简单的 x 和 y 对：

  if (check == 1 || check == 7) {
    // add current position to solution
    solution[x][y] = 1;

    // generate an array of all up/down/left/right points that are within bounds
    // - for a random path need to randomise the order of the points
    Point[] points = ... 

    for (Point next : points) {
      if (mazeUtil(next.x, next.y)) {
        // we've found the solution, so just return up the call stack
        return true;
      }
    }

    // this attempt failed, so reset the solution array before returning
    solution[x][y] = 0;

    return false;
  }

而且我认为这就是你对一只完全无知的老鼠所能达到的极限！要了解其工作原理，请考虑以下迷宫：

7 1
0 9

从“7”开始，可能的移动是向下和向右。

如果您先尝试 Down，它 return 是错误的，所以剩下的唯一选择是对，所以你最终得到了“1”。
如果您先尝试 Right，您仍然会得到“1”。

从“1”开始，可能的走法是向下和向左：

如果您先尝试 Down，它 return 为真，调用堆栈会冒泡 - 成功！
如果您先尝试向左，您最终会到达“7”，因此递归到上一步。

这就是所有可能发生的事情。所以使用 * 作为 return-false-backtrack，并且 !要想成功，以下任何一种都是可能的：

R-D!
R-L-D*-R-D!
R-L-R-L-R-L-R-L (keep going for a long, long time....) R-L-R-D!

所以对于一个可解的迷宫和一个真正的随机生成器，这最终会解开迷宫，尽管这可能需要很长时间。不过，需要注意的是，它并没有真正回溯那么多：只有从 2 或 0 节点开始的一步。

然而，仍然存在无法解决迷宫的问题，我认为对于一只完全无知的老鼠来说这是不可能的。这样做的原因是对于像这样的暴力递归，只有两种可能的终止条件：

目标已找到。
所有可能的路径都试过了。

而且对于一只完全无知的老鼠，没有办法检测到第二个！

考虑以下迷宫：

完全无知的老鼠会永远在顶行左右徘徊，所以程序永远不会终止！

解决这个问题的方法是老鼠必须至少有点聪明，并记住它去过的地方（这也将使可解决的迷宫运行在大多数情况下更快，而不是沿着整个路径回溯仅适用于单个节点）。但是，这个答案已经有点太长了，所以如果您对此感兴趣，我会在此处向您介绍我的其他迷宫解决答案：Java Recursive Maze Solver problems

哦，随机最后两点：

您不需要每次都创建一个新的 Random - 只需创建一个全局一个，每次都调用 nextInt。
nextInt(n) returns 在 0（含）和 n（不含）之间，所以你需要 nextInt(4) 而不是 nextInt(3).

希望这对您有所帮助！

二维迷宫求解器递归函数

2 dimensional maze solver recursive function

java

recursion

maze

backtracking

multidimensional-array