6.4 回溯法：进退有据的试探

6.4 回溯法：进退有据的试探

本节摘要：回溯法把解空间组织成一棵决策树，深度优先地走下去：能前进就做选择，走不通就撤销最后一步换条路。模板只有三个动作——选择、递归、撤销。全排列是它最小的完整样本；N 皇后展示剪枝的威力：四皇后十七个节点对暴力三百四十一个。本章承接 4.2 节 DFS 的骨架，把"遍历图"升级为"遍历决策空间"。

决策树：解空间的地图

很多问题的解没法算出来，只能"试"出来：排列、子集、棋盘布阵、路径搜索。它们的共同结构是一棵决策树——每层做一次选择，从根到叶是一条完整方案。全排列的决策树：第一层选谁打头（三种选择），第二层选谁第二（剩两种），第三层别无选择。

三个元素的全排列决策树

# 全排列：选择 → 递归 → 撤销，节点全程计数
def permutations(nums):
    n = len(nums)
    used = [False] * n
    path, out = [], []
    nodes = [0]
    def rec():
        nodes[0] += 1
        if len(path) == n:                 # 叶子：一份完整方案
            out.append(path[:])            # 必须拷贝，path 还会被回滚复用
            return
        for i in range(n):                 # 同层的所有选择
            if used[i]:
                continue                   # 剪掉用过的元素
            used[i] = True                 # 选择
            path.append(nums[i])
            rec()                          # 深入下一层
            path.pop()                     # 撤销
            used[i] = False
    rec()
    return out, nodes[0]

out, nodes = permutations([1, 2, 3])
print("全部排列：", out)
print("访问节点数：", nodes)
# 输出：
# 全部排列： [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
# 访问节点数： 16
# 1 个根 + 3 个一层节点 + 6 个二层 + 6 个叶子 = 16，与上图逐层对应
​

模板的灵魂是最后那两行撤销：path.pop() 与 used[i] = False。没有它们，上一条路径的残留会污染下一条，输出从"六种排列"变成同一条路径重复六遍。

剪枝：还没走到叶子就宣布此路不通

决策树最吓人的是规模：全排列的叶子是 n 的阶乘，八皇后的暴力枚举是 8 的 8 次方种摆法。剪枝在非叶节点就判断"这个分支不可能长出合法解"，整棵子树当场放弃。N 皇后：逐行放皇后，同列与两条对角线冲突即剪：

# N 皇后：冲突剪枝，节点数与暴力枚举对比
def nqueens(n):
    cols = [0] * n                         # cols[r]：第 r 行皇后所在列
    sols, nodes = [0], [0]
    def conflict(row, c):
        for r in range(row):
            if cols[r] == c or abs(cols[r] - c) == row - r:   # 同列或同对角线
                return True
        return False
    def rec(row):
        nodes[0] += 1
        if row == n:
            sols[0] += 1
            return
        for c in range(n):
            if conflict(row, c):
                continue                   # 剪枝：这格不行，整棵子树放弃
            cols[row] = c
            rec(row + 1)
            # cols 会被下一行覆盖，无需显式撤销（每层只写自己的下标）
    rec(0)
    return sols[0], nodes[0]

for n in (4, 6, 8):
    sols, nodes = nqueens(n)
    brute_nodes = sum(n ** k for k in range(n + 1))   # 暴力枚举的节点总数
    print(f"n={n}：解 {sols} 个；剪枝后访问 {nodes} 节点，暴力要 {brute_nodes} 节点")
# 输出：
# n=4：解 2 个；剪枝后访问 17 节点，暴力要 341 节点
# n=6：解 4 个；剪枝后访问 153 节点，暴力要 55987 节点
# n=8：解 92 个；剪枝后访问 2057 节点，暴力要 19173961 节点
# 八皇后：两千个节点对一千九百万个，剪掉九成九以上
​

剪枝的判断（conflict）每层只与上方已放的皇后比较，本身 O(n)，但换掉的是整棵指数级子树——用线性的检查换指数的分支，这是回溯能实战的根本原因。

剪枝其实分三个层次，越往上收益越大：可行性剪枝（这步都走不通，N 皇后的冲突检查）、最优性剪枝（这条分支就算走到底也不如已知解，交给下一节的限界）、对称性剪枝（这条分支与已探索的分支本质相同）。第三层最容易被漏掉：全排列天然无重复，但"从集合里挑组合"时，先选 a 再选 b 与先选 b 再选 a 是同一个组合——让候选从当前下标往后取（而非每次从头取），重复分支整片消失，连判重结构都省了。判重的哈希集合是花钱办事，起点后移是不花钱办事，能后者不前者。

⚠️ 常见坑：撤销不彻底或保存了引用。叶子处 out.append(path) 若忘写 path[:]，存进去的是同一个列表对象，回滚后所有"排列"都变成最后一条路径——六种排列变六份相同结果。凡是把可变对象存进结果集，先拷贝。

💡 关键直觉：回溯 = 决策树上的 DFS + 全局状态的"借还纪律"。选择时借、撤销时还，函数返回时全局状态必须与进入时一致——这条纪律守住，路径之间互不干扰。

走火入魔：搜索量失控与状态污染

**事故一：没有剪枝的回溯只是换了名字的暴力。**把 conflict 判断去掉，八皇后要摸近两千万个节点。剪枝条件宁早勿晚：越靠近根部剪掉一枝，省下的子树越大。

**事故二：把全局最优问题当回溯遍历。**只要一个最优解（而非全部方案）时，配合下一节的分支限界或可行的贪心动规，往往能提前终止；老老实实遍历整棵树，规模稍大就出不了结果。

**事故三：层间状态串味。**撤销漏了一行、或用了多层共享的临时容器，前一条路径的残影混入后一条。自检方法：在递归入口与出口各打印一次全局状态，两次输出应当完全一致。

本节要点回顾

• 解空间组织成决策树，回溯即树上的深度优先 + 撤销重试；三动作模板：选择、递归、撤销；
• 全排列最小样本：三个元素十六个节点、六片叶子，逐层可数；
• 剪枝是回溯的命门：N 皇后八阶两千节点对暴力近两千万节点，用线性检查换指数分支；
• 借还纪律：函数返回时全局状态与进入时一致；存结果先拷贝、撤销一步不落；
• 回溯适用于要全部方案或方案结构无法分解的场景——只要最优值时先考虑动规或下一节的限界。

走不通就回头是本能；走不通之前就算出来"此路注定不通"是本事。下一节：分支限界。