java - 理解回溯(迷宫算法)

Question

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

1) 从当前位置识别所有您之前未去过的开放位置，例如:向上、向下。 (左右可能被墙挡住了，也可能之前去过)

2) 如果amtOfOpenLocations >= 1随机选择openLocation并搬到那里。

3) (递归调用)如果没有出错，重复#1，直到到达路径或基本情况。

4) 如果amtOfMoveLocations < 1退一步完成每一个 Action ，直到其中一个 Action 有一个可用的移动位置，该位置不同于任何已经完成的 Action 。重复步骤 1-3。

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

如果我的逻辑是正确的，那么我的下一个问题是:

所以基本上我所做的就是不断检查已经创建的位置以外的位置，直到找到出路。当我找到出路时，我会忽略所有其他可能的移动并返回解决方案。例如，如果我在位置 (4,4)我有地点 (4,3), (4,5), (5,4), (3,4)全部可用 openLocations我是对这些位置中的每一个进行 4 次递归调用，还是只对其中任何一个进行一次递归调用并逐一测试每个位置？

我的书说“如果您不在导出点，请进行 4 次递归调用以检查所有 4 个方向，并提供 4 个相邻单元格的新坐标。”

安answer在 stackoverflow 上关于一个类似的问题说:“每次迭代多次移动......是错误的”因此，我很困惑。是我的书错了还是什么？

最后，防止我之前已经检查过的位置的最佳方法是什么？我的想法是保留一个临时数组，其中所有访问过的位置都用“!”标记和我的 getMoveLocations()方法将避免任何带有“!”的单元格。是否有更好的方法来执行此操作，或者我的方法是否可以接受？

Answer 1

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 中)连续出现在代码中的递归调用被连续执行。您将对它们中的每一个进行递归调用(您将如何通过 1 个调用访问 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，尽管其代码会稍微复杂一些。