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

Question

我正在尝试制作一个应该解决迷宫的应用程序，并且我正在尝试使用回溯技术来实现它。

我已经开发了一个代码，并适用于一些简单的场景，但至少在一个更复杂的场景中失败了。

在我公开代码和具体问题之前，我想解释一下它是如何工作的。

关于代码

所以我有两种方法 initializeMaze1 和 initializedMaze2，它们只是加载一些预设场景（起点、一些墙壁和终点）。

我对第一个没有问题，但随着第二个而改变。

Thouse方法给了我一个整数矩阵，它表示实体（墙，起点...）。

我还有一种用于净化的打印方法。

最后是迷宫方法，即回溯代码。参数为：

1. 生成的迷宫（由我之前讨论的方法完成）。

2. “玩家”在迷宫行中的位置。

3. “玩家”在迷宫列中的位置。

4. 解决方案。这是另一个矩阵，它将给出玩家的路径，所以我将在那里标记运动，并且我将原始迷宫解开。

现在我将更深入地讨论回溯代码。

回溯代码

所以这个方法是一个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]。