回溯法

回溯的口号是“试一个选择，走不通就撤销”，但它的真正价值不在枚举本身，而在于每一步维护的部分解不变量使“走不通”能够被尽早证明：砍掉一个深度为 $d$ 的节点，等于免去其下方可能指数多的叶子。与先生成全部组合再逐一检验的朴素做法相比，回溯把约束检查推进到构造过程内部，失败发现得越早越便宜。撤销这一动作保证兄弟分支在完全相同的状态下出发——这是把指数规模的搜索写成线性空间递归的代价与要点。

N 皇后问题逐行放置皇后，扩展时只生成与已放皇后不同列、不同两条对角线的位置。以 $4$ 皇后为例：完整枚举有 $4^4=256$ 个叶子，而回溯树小得多——第一行放第 $1$ 列后，第二行只剩 $2$ 个合法位置，多数分支在第三行即告枯竭，最终恰得全部 $2$ 个解。数独求解常配合“候选值最少的空格优先分支”的启发式，它只改变子节点的枚举次序与分支因子，不改变解集，因而不损害完备性。

边界有三。其一，剪枝必须是不可行性的证明：把“启发式评分低”当作剪枝条件会砍掉真解、破坏完备性；若为求近似解而接受这种截断，得到的是有损的启发式搜索，而非回溯。其二，原地修改共享状态时必须在返回前完全撤销（包括所有辅助标记），否则兄弟分支相互污染，产生难以复现的错误。其三，回溯与动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。的适用面不同：回溯遍历彼此不同的部分解，动态规划靠重叠子问题的缓存获利；子问题大量重复时应改用记忆化，几乎不重复时缓存只是浪费。

回溯是组合生成（排列公理库排列Permutation有限集合到自身的双射，或其元素的有序排列。、子集、划分的枚举）与约束满足求解的骨架：图着色公理库图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。、数独、拼图与调度都可写成逐变量赋值加剪枝。现代 SAT 求解器的祖先 DPLL 就是命题赋值上的回溯加单元传播；博弈树搜索中的 alpha–beta 剪枝、组合优化中的分支限界，都是“回溯加更强剪枝证书”的变体。与约束传播、对称性消除结合后，回溯在许多 NP 难问题的实际实例上远快于最坏界，但这仍不是多项式最坏保证。

若把搜索深度限制在参数 $k$，并证明每个节点至多产生 $b$ 个孩子，有界搜索树公理库有界搜索树Bounded search tree对局部障碍作完备分支，并让参数预算在每条分支严格下降。把运行时间写成 $O(b^k\mathrm{poly}(n))$，明确指数落在哪个参数上。迭代压缩公理库迭代压缩iterative compression逐步扩大实例，并把已有 k+1 解压缩为 k 解的参数化算法范式。沿实例规模逐步加入元素，同时把一个略超预算的解压回大小 $k$；测度与征服公理库Measure and Conquermeasure and conquer · 测度与征服用按局部状态加权的非整数测度分析分支算法，并联合优化所有规则的指数底数。则不用粗略“剩余变量数”，而为不同分支设计下降测度以解出更紧递推。它们都建立在可靠剪枝与完整撤销之上，却分别改变构造路线或分析尺度，不是三个同义的回溯模板。