java理解回溯（迷宫算法）

Question

我试图通过创建一个从迷宫中找到出路的算法来理解递归回溯。这就是我的“回溯”逻辑：

1）从当前位置中找出你以前没有去过的所有开放位置，例如：向上、向下。（左边和右边可能被墙挡住，或者以前可能去过）

2）如果amtOfOpenLocations >= 1选择一个随机的openLocation并移动到那里

3）（递归调用）如果没有任何问题，重复#1，直到到达一条路径或基本情况

4）如果amtOfMoveLocations < 1在每个移动中后退一步，直到其中一个移动有一个可用的移动位置，该移动位置是，而不是任何已经进行的移动。重复步骤1-3

所以我的第一个问题是：这是回溯算法的正确实现吗

如果我的逻辑正确，下面是我的下一个问题：

所以基本上我要做的是，我一直在检查除了已经制作的位置之外的其他位置，直到我找到一条出路。当我找到一条出路时，我会忽略所有其他可能的举措，并返回解决方案。例如，如果我在(4,4)位置，并且我的位置(4,3), (4,5), (5,4), (3,4)都可以作为openLocations使用，我是对其中的每个位置进行4次递归调用，还是只对其中任何一个位置进行一次递归调用，然后逐个测试每个位置

我的书说，“如果你不在出口点，进行4次递归调用，检查所有4个方向，输入4个相邻单元的新坐标。”

关于stackoverflow的一篇关于类似问题的文章说：“每次迭代多次移动……是错误的。” 因此，我感到困惑。我的书错了还是怎么了

最后，预防我之前检查过的位置的最佳方法是什么？我的想法是保留一个临时数组，其中所有访问的位置都标有“！”我的getMoveLocations()方法将避免任何带有“！”的单元格。有没有更好的方法，或者我的方法可以接受

Answer 1

我将尝试浏览所有要点：

1. 你的算法的轮廓看起来是正确的。第一步确保你不会陷入无限回归，因为你只尝试未访问的位置。只要你有地方可以尝试，你就会继续前进。在第3步，递归下降发生。第4步是递归函数的基本情况。这应该首先进行测试，就好像这是真的一样，您必须立即退出该函数。因此，它“一旦确定不可能完成一个有效的解决方案，就会放弃每个部分候选（“回溯”）（来自Wikipedia）
   通过随机选择一个新的openLocation，你也会让它变得不确定，但仍然是确定的。这是一种随机的

2. 您是对其中的每个位置进行4次递归调用，还是对其中任何一个位置进行一次递归调用，然后逐个测试每个位置？好你要做后者，在你的“组合树”中一个接一个地测试每个位置。回溯基本上是遍历一棵可能的组合树，然后向下找到解决方案，如果它卡住了，它就会向上移动。让我们把树的水平部分称为层
   你的书与你的书略有不同。虽然你有一个可以访问的地点列表，但你的书的作者似乎没有。他们将尝试一个位置的所有四个直接邻居，如果是墙，“出了问题”（第3步），他们会回溯。在这种情况下，他们不需要列表，只需要四个递归调用，一个接一个。同时，您可以从一个可能位置的列表中选择一个随机项，这些位置是为当前单元格预先计算的。请确保每次从递归下降中返回时不会重新计算该列表。为了使这些列表永久化并仅更新它们，它们不应在递归函数中，而是在开始回溯之前进行预计算，然后在每一步更新它们

3. 要么像本书的作者那样，在没有列表的情况下尝试，要么使用数组，这是正确的方法。我建议使用堆栈数据结构，这样就可以简单地弹出一个新位置，直到它为空

Answer 2

Is this a correct implementation of a backtracking algorithm?

是的，看起来不错

不过，向随机方向移动可能会增加代码的复杂性。如果做对了，不会太多，但仍然比确定地向上、向下、向左、然后向右移动要复杂一些

另外——如果你只有4个方向，那么作为一个单独的步骤，步骤1可能是多余的——只需在所有4个方向上循环（要么以确定的方式，要么将它们全部添加到一个列表中，然后随机选取一个并移除，直到列表为空），然后在递归调用之前进行访问/阻止检查应该简单得多

Do I make 4 recursive calls to each one of those locations or do I simply make one recursive call to anyone of them and test each location one by one?

我不知道你说的第二部分是什么意思。（在Java中）在代码中连续出现的递归调用会被连续执行。你会对每一个都有一个递归调用（你将如何用一个调用访问4个位置？）

An answer on stackoverflow about a similar problem says: "multiple moves per iteration...is wrong"

这听起来像是一个被误导的用户的胡言乱语

不过，基本思想还是有一定道理的——在迭代版本中，你可以在一次迭代中把许多动作排成一列，但每次迭代只执行一个动作。对于递归版本，它就不那么明显了

请看一下Wikipedia上的深度优先搜索伪代码，它显然会在每次迭代中进行多次递归调用/让多次移动排队：

Recursive:
1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

Iterative:
1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v ← S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

What would be the optimal way to prevent locations that I already checked before?

您的方法还不错，但更自然的方法是使用boolean数组，尽管上次我检查时，这并不是特别有效的内存。内存效率最高的是BitSet，尽管其代码稍微复杂一些