Skip to main content

回溯算法

回溯算法（Backtracking）是一种递归算法，用于解决一系列决策问题，它通过在每一步尝试所有可能的选项并逐步构建解决方案的方式来寻找问题的所有解。当算法发现当前的某个选择或步骤无法最终达到有效解时，它会取消（或“回溯”）上一步或几步的选择，并尝试其他可行的路径。

回溯算法通常用于解决诸如排列组合、划分问题、子集构造问题、解决数独游戏、八皇后问题等。这类问题通常可以表示为一个决策树，在这棵树中，每个节点代表一个决策阶段，每个分支代表取舍的一个选项。

回溯算法的基本步骤包括：

  1. 选择： 从多个选择中选择一个选项并向前推进。
  2. 约束： 检查当前的选择序列是否符合问题的约束条件，如果不符合，则剪枝，即放弃当前选择。
  3. 目标： 检查当前的选择序列是否满足问题的解条件，如果满足，则记录解或返回解。
  4. 回溯： 当当前选择无法达到目标或者无法继续向前推进时，回溯到上一步或几步，尝试其他的选择。

回溯算法的关键在于它能够系统地搜索问题的解空间，并且在不必要的情况下减少搜索，这通过剪枝来实现。剪枝是指在搜索过程中，提前排除那些显然不会得到解的路径，从而减少搜索的总量，提高算法的效率。

举一个简单的例子，假设有一个迷宫问题，我们要从起点走到终点。使用回溯算法，我们会尝试每一条可能的路径，每前进一步，都检查是否到达终点，或者是否遇到死路。如果发现当前路径无法成功到达终点，我们就回退一步，尝试其他的分支，直到找到正确的路径或者确定没有解。

回溯算法是一种非常强大的算法，但在最坏的情况下可能会有指数级的时间复杂度，因此在实际应用中需要谨慎使用，并尽可能地优化剪枝条件以提高效率。

  1. 用栈道存状态

解题模板

回溯算法是一种通过递归来遍历解空间以找到问题所有解的算法。它在解决问题时，如果发现现有的部分解不满足条件，就“回溯”到上一步，然后通过改变上一步的解继续尝试寻找问题的解。这种算法常用于解决组合问题、排列问题、划分问题等。

下面是回溯算法的一般步骤或解题模板：

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

这个模板可以分解为以下几个步骤：

  1. 路径：也就是已经做出的选择。
  2. 选择列表：也就是你当前可以做的选择。
  3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

具体步骤如下：

  1. 针对所给问题，确定递归函数的参数，包括选择列表和路径。
  2. 设置终止条件，当达到一个解时，应该记录下来，并且结束当前递归。
  3. 遍历选择列表，尝试可能的选择。
  4. 做出选择，即将当前的选择加入到路径中，并从选择列表中移除。
  5. 进入下一层决策树，即调用递归函数。
  6. 撤销选择，即将之前做出的选择从路径中移除，以便进行下一次的尝试。

在实际编码时，你可能需要根据问题的具体情况对模板进行适当的修改。例如，有时选择列表在递归过程中是不变的，有时你可能需要在递归之前创建新的选择列表，或者在做出选择后修改当前的选择列表。此外，如何记录解和如何剪枝（避免不必要的计算）也是实现回溯算法时需要考虑的问题。

应用场景

回溯算法是一种通过试错的方法来解决问题的算法，它尝试分步去解决一个问题。在每一步中，回溯算法尝试所有可能的选择，并继续前进，直到找到可能的解决方案或者直到所有的路径都被尝试过且失败。如果当前的选择和之前的选择一起不构成解决方案，回溯算法会取消上一步或几步的计算，再尝试其他的可能选择。这种算法经常用于解决以下类型的问题：

  1. 排列问题：

    • 需要找出一个集合的所有排列方式（如LeetCode 46题：全排列）。

  2. 组合问题：

    • 需要找出满足特定条件的所有组合方式（如LeetCode 77题：组合）。

  3. 子集问题：

    • 需要找出一个集合的所有子集（如LeetCode 78题：子集）。

  4. 括号生成问题：

    • 需要生成所有有效的括号组合（如LeetCode 22题：括号生成）。

  5. 数独问题：

    • 需要填充数独以解决游戏（如LeetCode 37题：解数独）。

  6. N皇后问题：

    • 需要在棋盘上放置皇后，使得她们互不攻击（如LeetCode 51题：N皇后）。

  7. 图的所有可能路径问题：

    • 需要找出图中从起点到终点的所有路径（如LeetCode 797题：所有可能的路径）。

  8. 单词搜索问题：

    • 需要在字母矩阵中寻找特定的单词（如LeetCode 79题：单词搜索）。

  9. 分割问题：

    • 需要将一个字符串分割成一些子串，使得每个子串都是一个回文串或满足其他条件（如LeetCode 131题：分割回文串）。

  10. 组合求和问题：

    • 需要找出所有可能的组合，这些组合的元素之和等于给定的目标数（如LeetCode 39题：组合总和）。

回溯算法的关键在于设置问题的解空间，以及如何在解空间中搜索到可能的解决方案。为了提高效率，通常会在回溯算法中使用剪枝技术，即在递归过程中排除那些明显不会得到解的路径，从而减少搜索空间，提高算法的效率。