Java 中的回溯

引言

回溯法是一种利用暴力搜索方法寻找所需解决方案的算法技术。简单来说，它会穷尽所有可能的解决方案，然后选择最优的一个。回溯法指的是在当前解决方案不可行时，回溯并探索其他替代方案的过程。因此，在这种方法中会用到递归。回溯法尤其适用于解决具有多种解决方案的问题。

回溯法是一种递归地求解问题的方法，它通过一次构建一个解的片段，并随着搜索的深入，及时放弃那些不可能产生解的枝（在搜索树的任何层级上）。

回溯法可以解决三种类型的问题：

• 决策问题 - 在此问题中，我们寻找一个可行解。
• 优化问题 - 在此问题中，我们寻找最优解。
• 枚举问题 - 在此问题中，我们找到所有可行解。

如何确定一个问题是否可以使用回溯法解决？

通常，任何具有清晰且明确的约束条件的问题，只要其候选解是逐步构建的，并且一旦确定候选解不可能完成为一个有效解，就会被放弃（“回溯”），都可以通过回溯法解决。然而，大多数已讨论的问题都可以使用其他已知的算法，如动态规划或贪心算法，以对输入大小而言的对数、线性、线性对数时间复杂度来解决，因此在各方面都优于回溯算法（因为回溯算法通常在时间和空间上都是指数级的）。尽管如此，仍有一些问题直到现在仍然只能通过回溯算法来解决。

想象一下你面前有三个盒子，只有一个盒子里有金币，但你不知道是哪一个。所以，为了得到金币，你必须一个接一个地打开所有的盒子。你首先会检查第一个盒子，如果里面没有金币，你必须关上它，然后检查第二个盒子，以此类推，直到找到金币。这就是回溯法，即一个接一个地解决所有子问题，以达到最佳可能的解决方案。

请看下面的例子，以便更正式地理解回溯法。

给定一个计算问题 P 的实例和与该实例对应的 D 数据，为了解决该问题需要满足的所有约束表示为 C。那么回溯算法将如下工作：

算法开始构建一个解决方案，从一个空的解决方案集 S 开始。

S = {}

向 S 添加第一个仍然可用的移动（所有可能的移动都一个接一个地添加到 S 中）。这会创建一个新的子树 s，位于算法的搜索树中。

检查 S+s 是否满足 C 中的每个约束。

如果是，则子树 s 可以添加更多子节点。

否则，整个子树 s 都无用，因此使用参数 S 回溯到步骤 1。

在新形成的子树 s 有资格的情况下，使用参数 S+s 回溯到步骤 1。

如果对 S+s 的检查表明它是一个针对整个数据 D 的解决方案。则输出并终止程序。

如果不是，则返回表明当前 s 无法找到解决方案，因此将其丢弃。

回溯法的伪代码

递归回溯解决方案。

N 皇后问题。

让我们尝试解决一个标准的“回溯法”问题，即 N 皇后问题。

N 皇后问题是指在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能相互攻击。例如，下面是 4 皇后问题的一个解决方案。

预期的输出是一个二进制矩阵，其中皇后放置的位置为 1。例如，下面是上面 4 皇后解决方案的输出矩阵。

{ 0, 1, 0, 0}

{ 0, 0, 0, 1}

{ 1, 0, 0, 0}

{ 0, 0, 1, 0}

回溯算法： 其思想是从最左边的列开始，逐列放置皇后。当我们在一列中放置一个皇后时，我们会检查与已放置的皇后是否有冲突。在当前列中，如果我们找到一个没有冲突的行，我们就将此行和列标记为解决方案的一部分。如果由于冲突找不到这样的行，我们就回溯并返回 false。

• 从最左边的列开始
• 如果所有皇后都已放置，则返回 true
• 尝试当前列中的所有行。对每个尝试过的行执行以下操作。
• 如果可以在此行安全地放置皇后，则将此 [行, 列] 标记为解决方案的一部分，并递归检查在此放置皇后是否会导致解决方案。
• 如果在此 [行, 列] 放置皇后会导致解决方案，则返回 true。
• 如果放置皇后不会导致解决方案，则取消标记此行、列，然后转到步骤 (a) 尝试其他行。
• 如果所有行都已尝试但没有任何成功，则返回 false 以触发回溯。

NQueensBacktracking.java

输出

0 0 1 0
0 2 0 1
3 1 0 0
2 0 1 0

时间复杂度 = O(N!)

N 皇后问题的回溯算法的时间复杂度为 O(N!)。这是因为算法需要探索棋盘上 N 个皇后的所有可能放置方式，而 N! 种可能的放置方式。

空间复杂度 = O(N*N)

N 皇后问题的回溯算法的空间复杂度为 O(N^2)。这是因为算法需要存储棋盘的表示，这需要一个 N x N 的二维数组。此外，算法需要存储一个堆栈来跟踪递归调用，这需要 O(N) 的空间。

结论

回溯法是一种强大的算法，可用于解决各种各样的问题。它通常用于解决解空间大或复杂的问题。

以下是一些可以使用回溯法解决的问题示例：

• 解决迷宫
• 解决数独谜题
• 找出集合中所有可能的组合
• 调度任务
• 找出两点之间的最短路径

回溯法是一种多功能算法，可用于解决各种问题。当其他算法，如蛮力搜索，速度太慢或不切实际时，通常会使用它。