高效状态空间搜索与剪枝策略解析

核心逻辑与数学原理

搜索的本质是在状态空间树（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 ans$。
• 上下界剪枝（Bound Pruning）：针对排列或组合搜索，通过预处理或数学推导，精确计算当前层变量 $x_i$ 的合法取值闭区间 $[L, R]$。通过严格限制 for 循环的枚举边界，消除无效的分支衍生。

状态设计与算法推导

以经典问题“生日蛋糕”（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$。
• 上界：由剩余体积与高度限制决定。

$$R_i \le \min\left(\lfloor \sqrt{N - v} \rfloor, last_r - 1\right)$$

$$H_i \le \min\left(\lfloor \frac{N - v}{R_i^2} \rfloor, last_h - 1\right)$$

3. 剪枝策略推导

• 可行性剪枝：预处理从第 $1$ 层到第 $i$ 层的最小体积和 $minV[i]$，最小侧面积和 $minS[i]$。若 $v + minV[dep] > N$，直接回溯。
• 最优性剪枝 1：若当前表面积加顶层最小侧面积已超全局最优，即 $s + minS[dep] \ge ans$，回溯。
• 最优性剪枝 2（数学推导放缩）：剩余体积 $N - v = \sum_{j=1}^{dep} R_j^2 H_j$。剩余侧面积 $\sum_{j=1}^{dep} 2 R_j H_j = \frac{2}{R_{dep+1}} \sum_{j=1}^{dep} R_j H_j R_{dep+1} > \frac{2}{last_r} \sum_{j=1}^{dep} R_j^2 H_j = \frac{2(N - v)}{last_r}$。由此可得强力最优性剪枝不等式：

$$s + \frac{2(N - v)}{last_r} \ge ans \implies \text{回溯}$$

C++ 标准源码

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int N, M;
int ans = 2e9;
int min_v[25], min_s[25];

// 状态：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) {
        if (dep == M) {
            s = cur_r * cur_r; // 蛋糕底面面积在第 M 层一次性计入
        }

        int max_h = std::min((N - v) / (cur_r * cur_r), h - 1);
        for (int cur_h = max_h; cur_h >= dep; --cur_h) {
            // 致命踩坑点：递归传递 s 时务必保证底面圆面积只在特殊处理时或首层计入，此处仅累加侧面积
            dfs(dep - 1, v + cur_r * cur_r * cur_h, s + 2 * cur_r * cur_h, cur_r, cur_h);
        }
    }
}

int main() {
    // 提升 I/O 效率，防止大数据量下超时
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    if (!(std::cin >> N >> M)) return 0;

    // 预处理前缀和，为剪枝提供边界数据
    for (int i = 1; i <= M; ++i) {
        min_v[i] = min_v[i - 1] + i * i * i;
        min_s[i] = min_s[i - 1] + 2 * i * i;
    }

    // 初始上界设定：半径和高度理论最大不可能超过 N
    dfs(M, 0, 0, N, N);

    if (ans == 2e9) {
        std::cout << 0 << "\n";
    } else {
        std::cout << ans << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 搜索顺序颠倒导致剪枝瘫痪 在没有依赖关系的前提下，应优先枚举“分支较少”或者“代价较大”的决策。例如在组合优化或剪枝题中，将 for 循环从大到小（从 max_r 到 dep）枚举，能够让较深层的状态尽早逼近全局最优解 $ans$，从而让后续的 s + min_s[dep] >= ans 剪枝高概率触发。若从小到大枚举，搜索树会发生极严重的左侧膨胀。
2. 整型截断与估价函数越界 在进行最优性剪枝的数学放缩时，类似 s + 2 * (N - v) / r 的表达式中，除法操作若直接使用整型会导致向下取整，导致估价出的下界偏小。在极端边界下，若刚好卡在最优解边缘，这种误差可能导致错误的剪枝（错杀正确解）。同时，在计算三次方、平方乘积时，若 $N$ 的范围增大（如部分变种题中），未转换为 long long 会引发数据溢出变负数，导致可行性剪枝失效，触发死循环。

经典 NOIP/洛谷 真题

1. 洛谷 P1120 小木棍

• 题意描述：若干根等长木棍随机砍成 $N$ 根长度不大于 50 的小木棍。给出砍断后的每根木棍长度，求原始木棍的最小可能长度。
• 问题本质：多重集合的等和子集划分问题。
• 核心解题思路：
• 上下界剪枝：原始木棍长度必在 [max_len, sum_len] 区间，且能被 sum_len 整除。
• 优化搜索顺序：对小木棍长度从大到小排序，先拼大木棍。
• 可行性剪枝（去重）：若当前木棍尝试失败，跳过后续所有相同长度的木棍；若在拼一根新木棍的开头就失败，或者在拼完一根木棍的最后一根时失败，直接判定当前原始长度非法，拒绝低效回溯。

2. 洛谷 P1434 滑雪

• 题意描述：给定一个二维网格，每个格子有其高度。只能从高处向低处四个方向滑行，求最长滑行轨道的长度。
• 问题本质：DAG（有向无环图）上的最长路搜索。
• 核心解题思路：
• 记忆化剪枝：属于可行性与重复性状态剪枝的终极形态。定义 $f[x][y]$ 为从 $(x,y)$ 出发的最长路径。
• 逻辑剪枝：在 DFS 过程中，若发现 $f[x][y]$ 已经被计算过，直接返回其值，将指数级搜索树剪枝退化为 $O(N \times M)$ 的线性图遍历，杜绝重复搜索相同子状态。