算法：回溯

回溯

回溯算法

回溯算法是一种通过穷举来解决问题的方法，核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止

回溯算法通常采用深度优先搜索来遍历解空间

尝试与回退

之所以称为回溯算法，是因为该算法在搜索解空间时会采用尝试与回退的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回至之前的状态，并尝试其他可能的选择。

剪枝

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”

框架代码

我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来，提升代码的通用性。state表示问题的当前状态，choices表示当前状态下可以做的选择

• Python

def backtrack(state: State, choices: list[choice], res: list[state]):
    """回溯算法框架"""
    # 判断是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
        return # 可选
    for choice in choices:
        # 剪枝：判断选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            # 进行下一轮选择
            backtrack(state, choices, res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

常用术语

• 解(solution)：解是满足问题特定条件的答案，可能有一个或多个
• 约束条件(constraint)：约束条件是问题中限制解的可行性的条件，通常用于剪枝
• 状态(state)：状态表示问题在某一时刻的情况，包括已经做出的选择
• 尝试(attempt)：尝试是根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解
• 回退(backtracking)：回退指遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态
• 剪枝(pruning)：剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率

优点与局限性

回溯算法本质上是一种深度优先搜索算法，尝试所有可能的解决方案直到找到满足条件的解。

优点在于可以找到所有可能的解决方案，加以合理的剪枝操作，具有很高的效率

但是在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受

• 时间复杂度可以达到指数阶或者阶乘阶
• 在递归调用中需要保存当前状态，当深度很大时，空间需求会很大

即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案，因为这些问题无法预测哪些选择可生成有效的解，因此必须对所有的可能进行遍历。因此关键是如何优化效率，有如下方法进行效率优化：

• 剪枝：避免搜索哪些肯定不会产生解的路径
• 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径

回溯典型例题