回溯法

回溯一边构造部分解，一边用约束判断它还能否完成：砍掉一个深度为 $d$ 的节点，等于免去其下方可能指数多的叶子。与先生成全部组合再逐一检验的朴素做法相比，回溯把约束检查推进到构造过程内部，失败发现得越早越便宜。撤销保证兄弟分支从相同的父状态出发，因此通常可以复用状态存储，无需为每个兄弟保留完整副本。

N 皇后问题逐行放置皇后，扩展时只生成与已放皇后不同列、不同两条对角线的位置。以 $4$ 皇后为例：不检查冲突的逐行枚举有 $4^4=256$ 个完整候选。只生成合法前缀时，各深度的节点数为 $1,4,6,4,2$，共 $17$ 个。第一行放第 $1$ 列后，第二行可放第 $3$ 或第 $4$ 列；前者在第三行无路可走，后者还能在第三行放第 $2$ 列，但第四行失败。另两条根叶路径给出全部 $2$ 个解。数独求解常配合“候选值最少的空格优先分支”的启发式，它只改变子节点的枚举次序与分支因子，不改变解集，因而不损害完备性。

枚举全部解时，剪枝必须是不可行性的证明：把“启发式评分低”当作剪枝条件会砍掉真解、破坏完备性；若接受这种启发式截断，就失去了枚举全部可行解的保证。

原地修改共享状态时必须在返回前完全撤销（包括所有辅助标记），否则兄弟分支相互污染，产生难以复现的错误。

模式匹配的回溯字节码理路回溯式模式匹配编译Backtracking pattern-match compilation · Pattern matching failure continuations用成功与失败标签生成线性大小的模式匹配字节码，保留首匹配绑定，并准确处理左偏or结构成功后的guard提交边界。提供一种固定候选顺序的应用：失败标签转下一模式，成功标签共享后续检查。它在行入口清空临时绑定，or两臂成功时覆盖相同名字集合；guard失败进入下一源行，不能重新尝试已经提交的or替代。这套有限无环IR的状态约束须单独证明，不能从“用了回溯”四个字自动得到。

回溯与动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。的适用面不同：回溯遍历彼此不同的部分解，动态规划靠重叠子问题的缓存获利；记忆化的收益取决于重复子问题的数量及重新求解它们的成本。

回溯是组合生成（排列理路排列Permutation有限集合到自身的双射，或其元素的有序排列。、子集、划分的枚举）与约束满足求解的骨架：图着色理路图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。、数独、拼图与调度都可写成逐变量赋值加剪枝。现代 SAT 求解器的祖先 DPLL 就是命题赋值上的回溯加单元传播。优化问题还允许另一类剪枝证书：整数规划分支定界理路整数规划的分支定界Branch and bound · Integer programming branch-and-bound用 LP 上界、整数可行解下界和完备变量分支管理搜索树，在所有未探索区域都失去改进可能时给出精确最优证书。用松弛界证明整棵子树不可能改善当前可行解，即使该子树仍有可行点也可以停止探索；这时目标是证明一个最优值，不是枚举全部解。与约束传播、对称性消除结合后，回溯在许多 NP 难问题的实际实例上远快于最坏界，但这仍不是多项式最坏保证。

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