回溯算法是什么？回溯的框架实现-js教程-PHP中文网

回溯算法是一种系统化尝试所有可能解的搜索策略，适用于组合、排列、子集、约束满足和路径寻找等问题，其核心在于通过“选择”推进搜索、通过“撤销选择”恢复状态以探索其他路径，从而在决策树上进行深度优先搜索并保证状态纯净；该算法的时间复杂度通常为指数级如o(n!)或o(2^n)，取决于问题的分支因子和深度，而空间复杂度主要由递归栈和当前路径存储决定，一般为o(n)。

回溯算法是什么？回溯的框架实现

回溯算法，在我看来，它就是一种有组织的暴力枚举，但又比纯粹的暴力聪明得多。它通过尝试构建问题的解决方案，如果发现当前路径走不通或者不符合要求，就立即“回溯”到上一步，撤销之前的选择，尝试另一条路径。这就像你在走迷宫，每到一个岔路口就选一条路走，如果走到死胡同，就退回到上一个岔路口，再选择另一条路，直到找到出口或者尝试完所有可能性。

回溯的核心，说白了，就是在一个决策树上进行深度优先搜索。每一次递归，我们都尝试做出一个选择；递归结束后，我们又撤销这个选择，为下一次尝试铺平道路。

def backtrack_framework(current_path, choices_left):
    # 1. 终止条件：当满足某个条件时，说明我们找到一个解或者当前路径无法继续
    if is_solution(current_path):
        add_to_results(current_path)
        # 如果只需要一个解，这里可以return True并向上层传递
        # 如果需要所有解，则继续探索其他分支
        # return

    # 2. 遍历所有可能的选择
    for choice in choices_left:
        # 2.1 做出选择：将当前选择加入路径，并更新剩余选择
        # 这一步可能涉及到修改原数据结构，或者创建新的副本
        make_choice(current_path, choice)
        update_choices_left(choices_left, choice) # 比如从choices_left中移除已选的

        # 2.2 递归调用：继续探索下一个决策层
        backtrack_framework(current_path, choices_left)

        # 2.3 撤销选择：这是回溯的关键！恢复到上一个状态，以便探索其他分支
        # 这一步确保了下一次循环迭代时，状态是干净的
        undo_choice(current_path, choice)
        restore_choices_left(choices_left, choice) # 比如将choice重新加回choices_left

登录后复制

这个框架里，

is_solution

登录后复制

是判断当前

current_path

登录后复制

是否已经构成一个完整且有效的解决方案。

make_choice

登录后复制

和

undo_choice

登录后复制

是对

current_path

登录后复制

和

choices_left

登录后复制

进行状态修改和恢复的操作。这套流程，从全排列到N皇后问题，几乎都可以套用。

回溯算法通常适用于哪些问题？

回溯算法，它的应用场景其实非常集中，主要就是那些需要“穷举所有可能路径”来找到解的问题。我个人觉得，当你遇到一个问题，感觉它像是在一个巨大的决策树里寻找特定节点，而且每一步选择都会影响后续可能性的时候，回溯往往就是你首先应该考虑的方案。

具体来说，它在以下几类问题中表现得尤为突出：

组合、排列、子集问题： 这是最经典的。比如给你一组数字，让你找出所有可能的子集，或者所有不重复的全排列。这些问题天然就带有“选择”与“不选择”或者“选择哪个”的决策过程。
- 例子： 找出数组
```
[1, 2, 3]
```
  登录后复制
  的所有子集
```
([], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3])
```
  登录后复制
  。
- 例子： 找出数组
```
[1, 2, 3]
```
  登录后复制
  的所有全排列
```
([1,2,3], [1,3,2], [2,1,3], ...)
```
  登录后复制
  。
约束满足问题： 这类问题通常有一些严格的规则需要遵守，你做的每一个选择都必须符合这些规则。如果某个选择导致后续无法满足规则，那就得回溯。
- 例子： N皇后问题：在N×N的棋盘上放置N个皇后，使得它们不能互相攻击。每放置一个皇后，都需要检查是否与已放置的皇后冲突。
- 例子： 数独求解器：在一个部分填充的数独网格中，填充剩余的数字，使得每一行、每一列和每一个3x3的小宫格内数字1-9只出现一次。
路径寻找问题： 在图或网格中寻找所有可能的路径，或者符合特定条件的路径。
- 例子： 寻找迷宫中的所有路径。
- 例子： 找出图中从起点到终点的所有简单路径。

虽然回溯算法在这些场景下非常有效，但也要清楚，它本质上是穷举，所以当问题规模变得很大时，性能会是一个挑战。不过，它的通用性和实现思路的清晰性，让它成为解决这类问题的首选工具。

算家云

高效、便捷的人工智能算力服务平台

查看详情

如何理解回溯算法中的“选择”与“撤销选择”？

“选择”与“撤销选择”，这是回溯算法最核心，也是最容易让人感到困惑的地方。我个人觉得，理解这两步的关键在于，它们共同维护了算法在不同决策路径之间切换时的“状态纯净性”。

“选择”（Make a Choice）： 当你站在一个决策点上，面对多种可能性时，你选择其中一个，并把它“加入”到你当前正在构建的解决方案中。这就像你在一个迷宫的岔路口，决定走左边那条路。
- 具体操作： 通常表现为将一个元素添加到结果列表（
```
current_path
```
  登录后复制
  ）中，或者修改某个状态变量（比如棋盘上的某个位置被标记为已占用）。
- 目的： 推动算法向更深层次的决策树分支探索。每次“选择”都是一次尝试，一次对潜在解决方案的构建。
“撤销选择”（Undo a Choice / Backtrack）： 这是回溯算法的精髓所在。当你沿着一条路径走下去，发现它是一条死路（比如走到了迷宫的死胡同），或者这条路径无法满足最终的条件，你就必须“返回”到上一个决策点。而为了能够尝试其他的选择，你必须把之前做的“选择”给“撤销”掉，让状态恢复到你做出那个选择之前的样子。这就像你从死胡同退回到岔路口，并且把之前走错的路留下的痕迹（如果有的话）清除掉，以便你可以尝试走右边那条路。
- 具体操作： 通常是把之前添加到结果列表中的元素移除，或者将之前修改的状态变量恢复到旧值。这个操作必须是“逆向”的，与“选择”操作完全对称。
- 目的： 恢复到父节点的“干净”状态，允许算法探索同一决策点的其他分支。如果没有这一步，状态就会被污染，后续的探索就会基于一个错误的前提，导致结果不正确或遗漏。

想象一下，你正在解一个数独。当你尝试在某个格子填入一个数字时，这就是一个“选择”。你继续填下一个格子。如果发现某个格子无论如何都无法填入合法数字，那就说明你之前某个选择是错误的。这时，你就会“回溯”到上一个填错数字的格子，把它清空（“撤销选择”），然后尝试填入另一个数字。

所以，“选择”是前进，“撤销选择”是后退，它们共同构成了回溯算法在解空间中“试探性探索”的机制。没有“撤销”，就没有“回溯”，算法就无法探索所有可能性。

回溯算法的时间复杂度和空间复杂度如何分析？

分析回溯算法的复杂性，往往比分析普通迭代算法要复杂一些，因为它的执行路径是动态的，取决于决策树的形状和剪枝策略。不过，我们还是可以从最坏情况和一般情况来把握。

时间复杂度：

回溯算法的时间复杂度通常是指数级的，因为它的本质是在一个决策树上进行深度优先搜索。最坏情况下，它可能需要遍历整个决策树。

决定因素：
- 决策树的深度（Depth）： 也就是递归的层数，通常与输入规模
```
N
```
  登录后复制
  相关。
- 每个决策点的分支数量（Branching Factor）： 在每个递归层，你有多少种选择。
粗略估计：
```
O(分支因子^深度)
```
登录后复制
。
具体例子：
- 全排列问题 (Permutations of N elements): 每个位置有
```
N
```
  登录后复制
  种选择，下一个位置有
```
N-1
```
  登录后复制
  种，以此类推。所以时间复杂度是
```
O(N!)
```
  登录后复制
  。这是非常高的，因为
```
N!
```
  登录后复制
  增长极快。
- 子集问题 (Subsets of N elements): 对于每个元素，你都可以选择“包含”或“不包含”，这构成了两个分支。因此，对于
```
N
```
  登录后复制
  个元素，有
```
2^N
```
  登录后复制
  种组合。时间复杂度是
```
O(2^N)
```
  登录后复制
  。
- N皇后问题： 虽然看起来也是
```
N!
```
  登录后复制
  级别，但由于剪枝（在放置皇后时检查冲突），实际运行时间会比
```
N!
```
  登录后复制
  小很多，但依然是指数级，大致是
```
O(N!)
```
  登录后复制
  的一个常数因子优化版本，或者说
```
O(N^N)
```
  登录后复制
  的一个优化版本。
剪枝（Pruning）的影响： 在实际应用中，我们经常会在回溯过程中加入“剪枝”操作，即在某个分支明显不可能得到解时，提前终止这个分支的探索。这能显著减少实际运行时间，但最坏情况下的理论复杂度可能不变。剪枝的有效性决定了算法的实际效率。

空间复杂度：

回溯算法的空间复杂度主要取决于两个方面：

递归栈的深度： 这是回溯算法最主要的额外空间消耗。每次递归调用都会在调用栈上创建一个新的栈帧。
- 通常： 递归栈的深度等于决策树的最大深度。对于大多数问题，这个深度与输入规模
```
N
```
  登录后复制
  成正比，所以是
```
O(N)
```
  登录后复制
  。
- 例子： N皇后问题，递归深度是
```
N
```
  登录后复制
  。全排列、子集问题，递归深度也是
```
N
```
  登录后复制
  。
存储当前路径/解决方案的辅助空间：
- 在递归过程中，我们需要一个数据结构来存储当前正在构建的解决方案（例如，一个列表或数组）。这个空间通常也与决策树的深度
```
N
```
  登录后复制
  成正比。
- 例子： 存储当前排列的列表，大小为
```
N
```
  登录后复制
  。存储当前子集的列表，最大大小为
```
N
```
  登录后复制
  。