核心逻辑与数学原理
搜索的本质是在状态空间树（State Space Tree）上进行遍历。面对指数级增长的状态空间，剪枝（Pruning）的底层逻辑是通过提前终止无效分支，将搜索复杂度从理论上界 $O(k^N)$ 压制到实际可运行的规模。
- 可行性剪枝（Feasibility Pruning）：在当前节点检测约束条件。一旦发现当前路径已无法满足合法性（如越界、资源耗尽），立即回溯。其数学表达为：设当前状态为 $S$，约束函数为 $g(S)$，若 $g(S) = \text{False}$，则切断以 $S$ 为根的整棵子树。
- 最优性剪枝（Optimality Pruning）：维护一个全局最优解 ans。在搜索过程中，若当前代价 $val(S)$ 加上后续估计的最小代价 $h(S)$ 已经大于或等于 ans，则该分支不可能催生更优解，直接终止。数学判定式为：$val(S) + h(S) \ge \text{ans}$。
- 上下界剪枝（Bound Pruning）：针对排列或组合搜索，通过预处理或数学推导，精确计算当前层变量 $x_i$ 的合法取值闭区间 $[L, R]$。通过严格限制 for 循环的枚举边界，消除无效的分支衍生。
状态空间树
什么是状态空间树？
状态空间树（State Space Tree）是一种逻辑和数学上的抽象模型。
解决一个问题时，所有可能的“走法”和“状态”，按照先后顺序画成的一棵大树。通过这棵树，我们可以把一个抽象的搜索问题，变成一个具象的“在树上找终点”的迷宫游戏。
核心构成要素
- 根节点（Root）：问题的初始状态。比如蛋糕题里“还没开始做蛋糕”，或者迷宫题里“站在起点”。
- 分支/边（Edges）：你的每一次决策或操作。比如在当前层选择半径 $R=5$，或者在迷宫里向东走一步。
- 内部节点（Nodes）：做出决策后达到的中间状态。它记录了你走到这一步时手里的“筹码”（如当前累计的体积、表面积、坐标等）。
- 叶子节点（Leaves）：搜索的终点。有两种可能：一种是触发了边界的合法解（成功做完蛋糕），另一种是无路可走的死胡同。
算法与状态空间树的关系
所有的搜索和优化算法，本质上都是在对这棵虚拟的树进行操作：
- DFS（深度优先搜索）：像一个死心眼的人，抓着一根树枝顺着往里死磕，直到撞到叶子节点，再退回上一个分叉口（回溯）。
- BFS（广度优先搜索）：像水流横向蔓延，先把第一层的分支全部走完，再同时进军第二层。
- 剪枝（Pruning）：顺着树枝往下走，在某个中间节点发现“再往下走绝对超重”或者“再往下走也不可能比已经找到的解更好”时，剪枝，少走冤枉路。
状态空间图与状态空间树
状态空间的本质往往是图（可能带环），但搜索算法的逻辑触角伸过去时，打量它的方式永远是一棵树。 我们写剪枝和防重逻辑，本质上就是在给这个充满环的图“剃头”，强行让它变成一棵干净、有穷的树。
状态设计与算法推导
以经典问题“生日蛋糕”（NOI1999 / 洛谷 P1731）为例。题目要求用总体积为 $N$ 的圆柱体搭建 $M$ 层蛋糕，自底向上半径 $R$ 和高度 $H$ 都为整数并且严格递减，求最小表面积。
1. 状态设计
搜索状态由当前层数、当前体积、当前表面积以及上一层的半径和高度共同决定。定义 DFS 函数状态：dfs(dep, v, s, last_r, last_h)。其中 dep 为当前正在搜索的层数（自底向上搜索，底为第 $M$ 层，顶为第 $1$ 层）。
2. 上下界推导
对于第 $i$ 层，体积和高度必须大于等于其上所有层的最小体积与高度之和。
- 下界：$R_i \ge i$，$H_i \ge i$。
- 上界：由剩余体积与高度限制决定，边界情况是高为1或半径为1。
$$R_i \le \min\left(\lfloor \sqrt{N - v} \rfloor, \text{last\_r} - 1\right)$$
$$H_i \le \min\left(\lfloor \frac{N - v}{R_i^2} \rfloor, \text{last\_h} - 1\right)$$
3. 剪枝策略推导
- 可行性剪枝：预处理从第 1 层到第 $i$ 层的最小体积和 $minV[i]$，最小侧面积和 $minS[i]$。若 $v + minV[dep] > N$，直接回溯。
- 最优性剪枝 1：若当前表面积加顶层最小侧面积已超全局最优，即 $s + minS[dep] \ge \text{ans}$，回溯。
- 最优性剪枝 2（数学推导放缩）：剩余体积 $N - v = \sum_{j=1}^{dep} R_j^2 H_j$。剩余侧面积满足：
$$\sum_{j=1}^{dep} 2 R_j H_j = 2 \sum_{j=1}^{dep} \frac{R_j^2 H_j}{R_j} > \frac{2}{\text{last\_r}} \sum_{j=1}^{dep} R_j^2 H_j = \frac{2(N - v)}{\text{last\_r}}$$
（建立了剩余侧面积和剩余体积的联系）
由此可得强力最优性剪枝不等式：
$$s + \frac{2(N - v)}{\text{last\_r}} \ge \text{ans} \implies \text{回溯}$$
可行性剪枝防的是“剩余体积太小”；而最优性剪枝 2 防的是“剩余体积太大” 最优性剪枝 1防的是：“当前已累积的表面积太大”（防的是“当前面积已经透支了未来层数的硬性低保开销”）。
最优性剪枝 2 是“基于体积资源”的动态可行性剪枝，那么最优性剪枝 1 就是“基于层数结构”的动态可行性剪枝。
最小体积
- 第 $1$ 层的最小体积就是：$1^2 \times 1 = 1^3$
- 第 $2$ 层的最小体积就是：$2^2 \times 2 = 2^3$
- 第 $3$ 层的最小体积就是：$3^2 \times 3 = 3^3$
要搭完剩下的 dep 层蛋糕，极端情况下，所需的体积和：
$$minV[dep] = \sum_{j=1}^{dep} j^3$$
最小表面积
- 第 $1$ 层的最小侧面积：$2 \times 1 \times 1 = 2 \times 1^2$
- 第 $2$ 层的最小侧面积：$2 \times 2 \times 2 = 2 \times 2^2$
- 第 $3$ 层的最小侧面积：$2 \times 3 \times 3 = 2 \times 3^2$
剩下 dep 层蛋糕所能达到的极限侧面积和就是：
$$minS[dep] = \sum_{j=1}^{dep} 2j^2$$
C++ 核心源码
// 状态：dep(当前层), v(累计体积), s(累计表面积), r(上一层半径), h(上一层高度)
void dfs(int dep, int v, int s, int r, int h) {
if (dep == 0) {
if (v == N) ans = std::min(ans, s);
return;
}
// 可行性剪枝：当前体积 + 顶层最小体积 > 目标体积
if (v + min_v[dep] > N) return;
// 最优性剪枝 1：当前表面积 + 顶层最小侧面积 >= 已知最优解
if (s + min_s[dep] >= ans) return;
// 最优性剪枝 2：利用数学不等式进行未来代价的下界估计
if (s + 2 * (N - v) / r >= ans) return;
// 上下界剪枝：自底向上枚举，优先尝试大尺寸（优化搜索顺序）
int max_r = std::min(static_cast<int>(std::sqrt(N - v)), r - 1);
for (int cur_r = max_r; cur_r >= dep; --cur_r) {
// 规避直接修改参数 s 导致的循环内状态污染，用局部变量计算底面贡献
int current_s = s + (dep == M ? cur_r * cur_r : 0);
int max_h = std::min((N - v) / (cur_r * cur_r), h - 1);
for (int cur_h = max_h; cur_h >= dep; --cur_h) {
dfs(dep - 1, v + cur_r * cur_r * cur_h, current_s + 2 * cur_r * cur_h, cur_r, cur_h);
}
}
}
// 从第 M 层开始(M是总层数)，当前体积为 0，当前表面积为 0，
// 虚拟的第 M+1 层半径和高度给一个足够大的边界值 N
dfs(M, 0, 0, N, N);
深度优先搜索优化的本质，是通过优化搜索顺序尽早确立全局最优解边界，进而协同上下界约束、可行性剪枝与最优性剪枝，实现对状态空间树的多维度动态裁剪。
NOIP 实战避坑指南
- 整型截断与估价函数的正确性
在进行最优性剪枝的数学放缩时，表达式
s + 2 * (N - v) / r中的整除操作会向下取整。由于向下取整使得估算出的未来代价下界比实际理论下界更小（更保守），因此它不会导致错误的剪枝（不会错杀正确解），但会略微减弱剪枝的强度。此外，在计算高次方乘积时，若 $N$ 的范围较大，未转换为long long会引发数据溢出变负数，导致可行性剪枝失效，触发死循环。
NOIP 实战避坑指南
- 搜索顺序
在无依赖关系的前提下，应优先枚举“约束能力强”（如尺寸或资源消耗较大）的决策。
自大到小调整搜索顺序的关键在于：一方面能利用大体量决策加速消耗资源，使后续子树的选择空间剧烈坍缩；另一方面能让算法在运行初期快速触达叶子节点，获取高质量基准解，从而显着收紧目标函数的全局上界 ans，激活后续的高概率、大面积剪枝。
反之，若从小到大枚举，由于浅层决策对资源的消耗极其缓慢，会导致搜索树在浅层发生指数级的状态空间膨胀；同时由于迟迟无法刷新 ans，会使整个搜索过程的最优性剪枝几乎全线瘫痪。
- 整型截断与估价函数的正确性
在针对最优性剪枝进行数学放缩时，表达式 s + 2 * (N - v) / r 中的整除操作会引入向下取整误差。由于该算术截断效应使得估算出的未来代价下界偏向保守，不会误杀潜在的最优解，仅在极微小程度上放宽了限界条件，在算法正确性上是安全的。
在进行高次幂的几何体积计算时，若数据边界较大，务必将中间变量显式转换为 long long 等高精度类型。否则，可行性剪枝会失效并TLE。
经典真题
1. 洛谷 P1120 小木棍
- 题意描述：若干根等长木棍随机砍成 $N$ 根长度不大于 50 的小木棍。给出砍断后的每根木棍长度，求原始木棍的最小可能长度。
- 问题本质：多重集合的等和子集划分问题。
- 剪枝策略：
- 上下界剪枝：原始长度 $L$ 的物理边界必然满足 $L \in [\max(stick), \sum stick]$。同时，由于所有原始木棍等长，在枚举 $L$ 时必须满足 $\sum stick \pmod L == 0$。
- 优化搜索顺序：小木棍长度从大到小排序，优先尝试长木棍。 长木棍的“物理约束强，组合灵活性差”，优先放置长木棍能使后续子树的选择空间剧烈坍缩；同时可以避免大量短木棍形成繁茂的低效浅层分叉。
- 可行性剪枝：同值冗余剔除。若当前
stick[i]尝试失败，则后续与之长度相同的木棍必然全部失败，直接通过while循环跳过指针。
/**
* @param res_sticks 还剩多少根原始木棍没有拼好
* @param cur_len 当前正在拼的这根原始木棍已经积累的长度
* @param last_idx 当前层循环枚举碎片的起始下标（避免组合重复）
*/
bool dfs(int res_sticks, int cur_len, int last_idx) {
if (res_sticks == 0) return true;
// 当前原始木棍完美拼完，开启一根全新木棍的拼接
if (cur_len == target_len) {
return dfs(res_sticks - 1, 0, 0);
}
for (int i = last_idx; i < n; ++i) {
if (visited[i] || cur_len + stick[i] > target_len) continue;
visited[i] = true;
if (dfs(res_sticks, cur_len + stick[i], i + 1)) return true;
visited[i] = false;
// 1. 首棍与末棍失败剪枝
if (cur_len == 0 || cur_len + stick[i] == target_len) return false;
// 2. 同值冗余剪枝（跳过后续相同长度的木棍）
while (i + 1 < n && stick[i] == stick[i + 1]) {
i++;
}
}
return false;
}if (cur_len == 0 || cur_len + stick[i] == target_len) return false; 首棍失败，代表“在最宽松的条件下（全新的空木棍），该首棍参与的任何搭配都无法完成全局所有木棍的拼接任务”。 末棍失败，代表“该木棍完美凑满当前 $L$ 后，后续其他木棍的拼接依然发生了全局崩盘”
2. 洛谷 P1434 滑雪
- 题意描述：给定一个二维网格，每个格子有其高度。只能从高处向低处四个方向滑行，求最长滑行轨道的长度。
- 问题本质：DAG（有向无环图）上的最长路搜索。
- 核心剪枝策略：
记忆化剪枝：属于重复性状态剪枝。定义
f[x][y]为从(x, y)出发的最长路径。若发现f[x][y]已经被计算过，直接返回其值，将指数级搜索树剪枝优化为 $O(N \times M)$ 的线性图遍历。
int dfs(int x, int y) {
if (f[x][y] > 0) return f[x][y]; // 记忆化剪枝，直接返回已知状态
int max_len = 1;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] < grid[x][y]) {
max_len = std::max(max_len, dfs(nx, ny) + 1);
}
}
return f[x][y] = max_len; // 记录当前状态的最优解
}