回溯算法 - 权威教程

什么是回溯算法？

回溯是一种算法，它通过搜索可能的组合来解决计算问题。它逐步构建候选方案，并移除那些不满足给定约束条件的方案。当需要从多个可能结果中选择一个可行方案时，这种技术非常有用。

这种算法被认为比暴力破解方法更好、更有效。与尝试所有可能解决方案的暴力破解不同，回溯侧重于根据给定的约束条件只寻找一个最终解决方案。当遇到死胡同时，它通过撤销上一步（回溯）并尝试其他选项来节省时间和内存。此外，一旦找到有效解决方案，它就会停止。

回溯是一种广泛使用的技术，因为它可以解决复杂问题而无需耗尽资源。它对于必须满足许多约束条件的问题特别有用，例如数独、N皇后问题和调度问题。通过智能地遍历潜在解决方案，回溯可以找到满足所有条件的答案。这使其对于需要精度和效率的任务都非常有价值。

回溯算法如何工作？

回溯算法是一种逐步寻找有效解决方案的问题解决技术。如果一个步骤的约束条件不满足某些条件，算法就会返回到上一步。

然后，它会继续尝试满足给定约束条件的其他可能组合。由于存在许多可能的组合，它会选择最令人满意的选项之一，并顺序解决问题。当需要解决一个或多个可能选项时，这种算法技术非常有用。撤销意味着在出现无法产生有效解决方案的情况时取消您的选择。

回溯算法通常具有以下步骤来解决问题：

步骤 1) 初始化：从一个初始的空/部分解决方案开始。

步骤 2) 选择：根据特定的标准和约束条件，选择一个选项来扩展当前解决方案。

步骤 3) 探索：通过考虑所选的候选方案并在解决问题的过程中前进，递归地求解。

步骤 4) 约束检查：在每一步检查当前的部分解决方案是否违反任何约束条件。如果违反，则回溯到上一步并尝试不同的候选方案。

步骤 5) 终止：当找到有效解决方案或所有组合都已用尽时，回溯过程停止。

步骤 6) 回溯：如果当前选项未能解决给定问题，它将返回到之前的状态。然后它会考虑新的选项来解决给定问题。

步骤 7) 重复：继续执行这些步骤，直到问题得到解决或所有选项都被探索。

回溯算法的递归性质

回溯算法本质上是递归的。这意味着算法会使用不同的参数调用自身，直到找到解决方案或测试了所有可能性。

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

回溯问题相关常用术语

以下是一些与回溯技术相关的基本术语：

解决方案向量：将解决方案表示为 n 元组，例如 (X1, X2, …, Xn)。
约束：限制 X 值的规则，包括隐式和显式约束。
解空间：所有满足显式约束的有效 X 值。
状态空间树：将解空间表示为一棵树。
状态空间：描述状态空间树中的路径。
问题状态：搜索树中表示部分解决方案的节点。
解决方案状态：构成 S 中有效解决方案元组的状态。
答案状态：满足隐式约束并产生所需解决方案的状态。
有希望的节点：导致所需解决方案且保持可行的节点。
无希望的节点：导致不可行状态，不进一步探索。
活动节点：已生成但尚未扩展子节点。
E 节点：正在生成子节点的活动节点。
死节点：所有子节点都已生成，但不再进一步扩展。
深度优先节点生成：使用最新的活动节点作为下一个 E 节点。
边界函数：最大化或最小化 B(x1, x2, …, Xa) 以用于优化。
静态树：独立于问题实例的树形结构。
动态树：与问题实例相关的树形结构。

何时使用回溯算法？

当出现以下情况时，我们可以选择回溯技术来解决复杂问题：

存在多种选择：如果问题解决过程的每一步都有许多选项，回溯就很合适。这些选项可能与项目选择和移动有关。
没有明确的最佳选择：当信息不足以确定可用选项中的最佳选择时，可以使用回溯算法。
决策导致更多选择：您可以选择回溯技术来系统地审查选择。
需要探索所有可能的解决方案：回溯通过一系列相互构建的决策来系统地探索所有解决方案。

回溯问题的类型

回溯算法中有三种类型的问题：判定问题、优化问题和枚举问题。下面我们来学习它们。

判定问题：在此类问题中，目标是确定是否存在可行解决方案。我们检查“是”和“否”的答案。例如，N皇后问题。这是一个判定问题，它考察在 N×N 棋盘上放置 N 个皇后而不相互攻击的可能性。
优化问题：在优化问题中，目标是在许多选项中找到最佳解决方案。这可能涉及确定某个函数或变量的最大值和最小值。例如，考虑背包问题，其目标是在遵守重量限制的同时，最大化背包中物品的总价值。
枚举问题：其目标是找到给定问题的所有可能解决方案。我们列出所有有效的选项，没有任何遗漏。一个例子是生成给定字符集的所有可能字母组合。

回溯的应用与示例

回溯有各种应用。其中一些应用及其伪代码在下面进行了解释。

数独解算器：这个问题包含一个包含重复数字的 3×3 子网格。回溯技术将显示解决方案返回 false，表明需要放置不同的数字。

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

N皇后问题：回溯方法确定如何在 N×N 棋盘上放置皇后，以便它们都不会相互威胁。

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

子集和问题：它用于从给定集合中找到加起来等于特定目标和的数字子集。

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

哈密顿回路问题：回溯可用于在图中找到访问每个顶点恰好一次的闭合回路。
迷宫中的老鼠问题：回溯技术用于找到老鼠从迷宫起点到出口的路径。

回溯算法的优缺点

回溯算法的优点

回溯技术用于解决复杂问题。它有很多优点，例如：

回溯技术对于处理约束条件非常有效。
这种方法在解决优化问题方面效果很好。
该技术适用于各种类型的问题。
这个过程可以帮助审查所有可能的解决方案。
由于它会回溯，因此比暴力破解技术节省更多内存。

回溯算法的缺点

回溯技术也有一些限制，例如时间复杂度。该技术有以下缺点：

不保证有解决方案。
由于组合众多，速度较慢。
由于可能性众多，时间复杂度很高。
它不适用于实时约束，因为找到最佳解决方案可能需要很长时间。
效率取决于问题的复杂程度。

回溯与递归的区别

递归	回溯
调用自身直到达到基本情况。	使用递归来审查所有可能性，直到找到最佳可行结果。
自底向上方法。	自顶向下方法。
不丢弃任何值。	拒绝不可行的解决方案。

结论

回溯是一种有用的算法策略，通过系统地探索可行解决方案并在必要时回溯来解决复杂问题。随着计算能力和算法效率的提高，我们可以期望回溯技术得到改进。这些进步将使它们能够更有效地处理更大、更复杂的问题。

此外，机器学习模型可以根据先前学习的模式来指导回溯决策。

所有这些技术创新将彻底改变回溯算法，使其成为解决各个领域复杂问题的强大而多功能的工具。