剪枝CSP-S

💡 核心思想

剪枝是在搜索过程中，通过某些条件判断提前排除不可能产生最优解的子树，从而减少搜索量。常见策略：可行性剪枝、最优性剪枝（上下界剪枝）、冗余剪枝。

🎯 直觉理解

剪枝就是"提前砍掉没希望的分支"：搜索过程中一旦发现当前状态不可能优于已知最优解（或不可能满足条件），立刻停止深入，省下大量时间。

两类剪枝：可行性剪枝（这条路径已经不可能合法，如八皇后某列已占）和最优性剪枝（就算继续走也不可能比当前最优好，如背包搜索中剩余价值加满也超不过答案）。

好剪枝的标准是"砍得多且不会砍错"。先写出暴力搜索，再针对卡住的数据点分析哪类分支白费时间——剪枝题考的就是这个分析能力。

📝 算法流程

1. 可行性剪枝：当前状态已经不满足约束，直接回溯
2. 最优性剪枝：当前代价已经超过已知最优解，不用继续
3. 排序优化：按某种顺序搜索，更早找到优解
4. 记忆化：相同状态不重复搜索

$$\text{剪枝后的搜索量} \ll \text{朴素搜索量，但最坏情况不变}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
// 剪枝示例：子集和问题
int n, target, a[25];
bool dfs(int i, int sum) {
    if (sum > target) return false;      // 可行性剪枝
    if (i == n) return sum == target;
    // 最优性剪枝：即使全选也不够
    if (sum + /* remaining sum */ 0 < target) return false;
    if (dfs(i+1, sum + a[i])) return true;  // 选
    if (dfs(i+1, sum)) return true;          // 不选
    return false;
}
int main() {
    cin >> n >> target;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n, greater()); // 大的先试，更早触发剪枝
    cout << (dfs(0, 0) ? "Yes" : "No") << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目