关于使用回溯java解决迷宫的问题

Question

我正在尝试制作一个应该解决迷宫的应用程序，并且我正在尝试使用回溯技术来实现它。我已经开发了一个代码，并适用于一些简单的场景，但至少在一个更复杂的场景中失败了。在我公开代码和具体问题之前，我想解释一下它是如何工作的。关于代码所以我有两种方法 initializeMaze1 和 initializedMaze2，它们只是加载一些预设场景（起点、一些墙壁和终点）。我对第一个没有问题，但随着第二个而改变。Thouse方法给了我一个整数矩阵，它表示实体（墙，起点...）。我还有一种用于净化的打印方法。最后是迷宫方法，即回溯代码。参数为：生成的迷宫（由我之前讨论的方法完成）。“玩家”在迷宫行中的位置。“玩家”在迷宫列中的位置。解决方案。这是另一个矩阵，它将给出玩家的路径，所以我将在那里标记运动，并且我将原始迷宫解开。现在我将更深入地讨论回溯代码。回溯代码所以这个方法是一个for循环，它尝试一些尝试（尝试是玩家可能的移动），所以我们尝试每个人，直到我们获得有效的移动或返回，因为没有可能的有效移动。我有一个isFactible方法，可以分析运动并说它是否正常（如果撞到墙上或如果超出限制）。如果 不可行，则尝试其他移动（增加 for 循环的迭代变量）。如果 是 不可行的，我们完成循环，取消标记实际位置并返回一个 false 值（因此其他上下文将知道它）。如果是事实，我们将标记新位置，我们需要在两种可能性之间进行区分：我们要移动的位置是结束（服从或退出），所以我们成功了。我们要移动的位置不是终点，所以我们再次递归地调用我们已经移动的新位置。现在我要谈谈我发现的问题。问题当我加载第二个迷宫时，我们有这个场景：S：开始。爱因斯坦：空。W： 墙。女：完成。|S|E|W|W||E|E|E|E|这是问题所在|E|E|W|W||W|E|E|F|所以代码，尝试先向右移动，如果没有，请尝试向下移动，如果不尝试左移，如果没有，请尝试向上移动。我们有预设运动。所以向右移动，好吧。然后试图再次向右移动，但有一堵墙。所以下去，好吧。然后，向右移动，直到最后一列。试图向右移动，他不能，因为出去了。试图向下移动，他不能，有一堵墙。试图向左移动，他可以，所以移动到那里。我有这个无限循环。我想的第一件事是，好吧，只要增加更多的限制，避免他可以移动到他已经去过的地方。但我不认为这是一个好的解决方案。您知道如何解决此问题吗？也许，如果我在代码中犯了一些错误，或者如果我选择的解决问题的策略不好，我将不胜感激您的意见。谢谢你。

Answer 1

就像你（想想你）解决一个真正的迷宫一样。

对于每个位置，请记录您从哪个方向到达以及您离开的（有效）方向（我想在你离开之前）。

当您返回某个位置（应该允许重新访问）时，将已经尝试过的方向视为与墙壁相同的方式 - 即它是无效的。

当你没有更有效的方向时，回到你来的时候。

因此，与代码的唯一区别是记住每个位置的“尝试和失败”方向。这应该足以防止递归。

Answer 2

正如DrPhill所说，你必须跟踪你去过的地方。你已经在函数中这样做了，但你没有在函数中使用这些信息。markcheckValidMovement

您应该将该函数更改为如下所示：

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement, int[][] solution)

  {

    if(checkNotOutOfBounds(maze, stepX, stepY, movement) 

        && checkNotCollideWithObstacle(maze, stepX, stepY, movement)

        && isNotYetVisited(maze, stepX, stepY, movement, solution))

    {

      return true;

    }

    return false;

  }   

其中，如果 at 下一步不相等，则函数返回 false。isNotYetVisitedsolution1

希望这有帮助。

Answer 3

我认为最简单的方法是记住你最后一次存在的坐标。如果除了回去之外没有其他有效的动作，请返回并将您所在的位置标记为墙壁。最后，您将到达 [F]。