我试图通过创建一个算法来理解递归回溯，该算法可以从迷宫中找到出路。这就是我的“回溯”逻辑：
1）从当前位置识别所有打开的位置，这些位置之前您没有去过，例如：上、下（左右两边可能被墙堵住了，也可能以前去过）
2）如果amtOfOpenLocations >= 1选择一个随机openLocation并移动到那里。
3）（递归调用）如果没有出错，则重复#1，直到到达路径输出或基本情况。
4）如果amtOfMoveLocations < 1后退一步，直到其中一个移动有一个可用的移动位置，而不是任何已进行的移动。重复步骤1-3。
所以我的第一个问题是：这是回溯算法的正确实现吗？
如果我的逻辑正确，下面是我的下一个问题：
所以基本上我要做的就是在找到出路之前不停地检查其他地方。当我找到出路时，我忽略了所有其他可能的行动，并返回解决方案。例如，如果我在location(4,4)中，并且我的locations(4,3), (4,5), (5,4), (3,4)都可用作openLocations我是对其中每个位置进行4次递归调用，还是只对其中任何一个位置进行一次递归调用并逐个测试每个位置？
我的书说：“如果你不在一个退出点，做4个递归调用检查所有4个方向，喂养4个相邻细胞的新坐标。”
stackoverflow上的一个关于类似问题的answer说：“每次迭代多次移动……是错误的”
所以我很困惑。我的书是错了还是怎么了？
最后，什么是防止我之前已经检查过的位置的最佳方法？我的想法是保留一个临时数组，所有访问过的位置都用“！”我的getMoveLocations()方法可以避免任何带有“！”。有更好的方法来做这件事吗？还是我的方法可以接受？
最佳答案
这是回溯演算法的正确实作吗？
是的，看起来很好。
但是，在一个随机的方向上移动可能会增加代码的复杂性。不多，如果做得对，但仍然有点复杂，比确定地移动上，下，左，然后右，例如。
另外-如果您只有4个方向，那么作为单独步骤的步骤1可能会过多—只需在所有4个方向上循环（确定地循环，或者将它们全部添加到一个列表中并随机选择其中一个并将其移除，直到列表为空），然后在递归调用之前执行访问/阻止检查应该简单得多。
我是对这些位置中的每个位置进行4次递归调用，还是只对其中任何一个位置进行一次递归调用并逐个测试每个位置？
我不知道你说的第二部分是什么意思（在Java中）在代码中连续出现的递归调用按序列执行。您将对每个调用都有一个递归调用（如何使用一个调用访问4个位置？）是的。
stackoverflow上关于类似问题的一个答案是：“每次迭代多次移动……是错误的”
听起来像是被误导的用户胡言乱语。
不过，基本思想还是有一定意义的——在迭代版本中，您在一个迭代中对许多移动进行排队，但每次迭代只执行一个移动（其中pop）。对于递归版本，这一点不太明显。
查看Wikipedia上的depth first search伪代码，它清楚地使每次迭代都有多个递归调用/队列多个移动：
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)
什么是防止我之前已经检查过的位置的最佳方法？
你的方法不错，但更自然的方法是使用
boolean数组，不过，上次我检查时，这并不是特别有效的内存。内存效率最高的是aBitSet，尽管其代码稍微复杂一些。关于java - 了解回溯(迷宫算法)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23712737/