专题：搜索（一）—— 回溯与剪枝

本讲定位（先把话说清楚）：cspj-series/cspj-round2-analysis-2019-2025.md 与 csps-series/csps-round2-analysis-2019-2025.md 的逐题统计给出的结论是——

回溯搜索在 CSP-J 复赛七年 28 题、CSP-S 复赛七年 30 题里，一次都没有作为满分算法的主考点出现过。但它是几乎每道 T3/T4 部分分档的通用手段。

所以本讲的定位是保底拿分，不是拿满分。把同样的时间投在 DP 上，边际收益更高（DP 在 J 组复赛 5 次主考点、且全部落在 T3/T4）。

⚠️ 本线总纲曾把这一讲称作”全库最大的空白”——那个说法写在复赛统计做出来之前，数据不支持”最大”这个形容，已在总纲第 8 节修订。 但”空白”这半句仍然成立：graph-series/02、03 只讲了图上的遍历，解空间自己生成的那一半搜索，全库确实一篇没有。本讲补的是这一半。

本讲实测

⚠️ 编译选项：本讲代码块由 tools/check-cpp-blocks.py 用 g++ -std=c++11（不开 -O2） 编译运行，下列耗时即该环境实测。本讲的核心指标是”搜索树结点数”，它与编译选项完全无关——这是搜索类实测比耗时类实测更可靠的地方。

可行性剪枝的收益随规模指数级放大。 八皇后从”枚举全排列最后检查”改成”边放边检查”，搜索树结点数在 $n=4$ 时只省 3.82 倍，$n=9$ 时省 117.51 倍——剪枝越晚做，浪费越大。
对称性剪枝的收益约为 2 倍，且只对偶数 $n$ 满额。 实测偶数 $n$ 趋近 2.00x（$n=4$ 是 1.89x、$n=6$ 是 1.99x，$n\ge8$ 的偶数恰好 2.00x），奇数 $n$ 只有 1.69~1.83x——因为中间那一列自己镜像还是自己，必须单独算、不能翻倍。
⚠️ 搜索顺序本身就是剪枝，而且效果比想象中大。 0/1 背包（$n=26$）在完全相同的剪枝代码下，物品按性价比降序排 54987 个结点，按升序排 721306 个——差 13.1 倍。什么都不排是 417604 个。
最优性剪枝比可行性剪枝重要得多。 同一个背包：只做可行性剪枝要 7500 万～7800 万个结点，加上最优性剪枝后降到 5.5 万～72 万个——省了 95.5 ～ 1366.9 倍。
⚠️ vis[i] = false 那一行写错的三种后果，量级完全不同：漏写 → 恒定只生成 1 个排列（不管 $n$ 多大）；写在递归之前 → 生成 $n^n$ 个（$n=9$ 时 387420489 个，是 $n!$ 的 1068 倍）；撤错下标（vis[d] 写成了 vis[i] 该在的位置）→ 生成 $n!\cdot(n+1)/2$ 个。三种都不报错，只是答案错。
剪枝能把可行规模从 $n\le11$ 推到 $n\le15$ 以上。 质数环问题：next_permutation 全排列在 $n=11$ 要枚举 39916800 个、用 1.077 秒；回溯 + 剪枝只访问 25930 个结点（少 1539.4 倍）、用 0.0010 秒，且能一路推到 $n=15$（3429090 个结点，0.1676 秒）。
回溯与 DP 的分界可以量化。 网格路径计数里，纯递归的结点数 / 记忆化的状态数在 $n=12$ 时是 61542 倍——状态重复率高就该记忆化。而八皇后的状态不会重复，记忆化没有任何意义。

前置与适合对象

前置：

basic-series/04-enumeration-simulation-construction.md —— 本讲直接接第 04 讲的两个钩子（见 §3、§2.3）。
dp-series/01-recursion-to-dp.md —— §4 的分界要用到”记忆化搜索”。
GESP 五级第 06 讲（递归）已经讲过递归的执行流程与栈帧。本讲不重讲递归本身，只讲”递归 + 状态撤销”这个组合。

适合对象：CSP-J 复赛（本讲的 §1、§2.1、§2.3 够用）；CSP-S 复赛（全讲，重点 §2.2 与 §2.4）。

本讲不讲（只指路）：