剪枝入门

概念讲解

什么是剪枝？

剪枝是在搜索过程中，提前排除不可能产生最优解的分支，从而减少搜索空间。

剪枝的类型

1. 可行性剪枝： 排除不满足约束条件的分支
2. 最优性剪枝： 排除不可能产生最优解的分支
3. 对称性剪枝： 排除对称的分支
4. 记忆化剪枝： 避免重复计算

可行性剪枝

示例：N 皇后问题

123456789101112131415161718bool col[100], diag1[100], diag2[100];

void solve(int row, int n, int& count) {
    if (row == n) {
        count++;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        if (col[i] || diag1[row + i] || diag2[row - i + n]) {
            continue;  // 剪枝：不满足约束条件
        }
        
        col[i] = diag1[row + i] = diag2[row - i + n] = true;
        solve(row + 1, n, count);
        col[i] = diag1[row + i] = diag2[row - i + n] = false;
    }
}

最优性剪枝

示例：0-1 背包

12345678910111213141516171819202122232425int maxValue = 0;

void dfs(int index, int currentWeight, int currentValue, int n, int W, int w[], int v[]) {
    if (index == n) {
        maxValue = max(maxValue, currentValue);
        return;
    }
    
    // 剪枝：当前价值加上剩余所有物品的价值也不可能超过最优解
    int remainingValue = 0;
    for (int i = index; i < n; i++) {
        remainingValue += v[i];
    }
    if (currentValue + remainingValue <= maxValue) {
        return;
    }
    
    // 选择当前物品
    if (currentWeight + w[index] <= W) {
        dfs(index + 1, currentWeight + w[index], currentValue + v[index], n, W, w, v);
    }
    
    // 不选择当前物品
    dfs(index + 1, currentWeight, currentValue, n, W, w, v);
}

常见剪枝技巧

1. 排序剪枝

先搜索价值大的分支，更容易找到较优解，从而剪掉更多分支。

2. 上下界剪枝

维护当前最优解，如果当前解加上剩余可能的解也不可能超过最优解，则剪枝。

3. 对称性剪枝

避免搜索对称的分支。

4. 记忆化剪枝

使用数组记录已经计算过的状态，避免重复计算。

考点分析

初赛考查方式

1. 选择题： 剪枝的概念
2. 程序阅读： 理解剪枝过程
3. 编程题： 剪枝应用

常见题型

• N 皇后问题
• 数独求解
• 搜索优化

例题精讲

例题 1：N 皇后问题

题目： 在 n×n 的棋盘上放置 n 个皇后，使得它们互不攻击。

解答：

123456789101112131415161718192021222324252627282930313233#include <iostream>
using namespace std;

bool col[100], diag1[100], diag2[100];
int count = 0;

void solve(int row, int n) {
    if (row == n) {
        count++;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        if (col[i] || diag1[row + i] || diag2[row - i + n]) {
            continue;
        }
        
        col[i] = diag1[row + i] = diag2[row - i + n] = true;
        solve(row + 1, n);
        col[i] = diag1[row + i] = diag2[row - i + n] = false;
    }
}

int main() {
    int n;
    cin >> n;
    
    solve(0, n);
    
    cout << count << endl;
    
    return 0;
}

练习题

1. 洛谷 P1219 八皇后

12345678910111213141516171819202122232425262728293031323334353637#include <iostream>
using namespace std;

bool col[20], diag1[40], diag2[40];
int path[20];
int n, count = 0;

void dfs(int row) {
    if (row == n) {
        count++;
        if (count <= 3) {
            for (int i = 0; i < n; i++) {
                cout << path[i] + 1 << " ";
            }
            cout << endl;
        }
        return;
    }
    
    for (int i = 0; i < n; i++) {
        if (col[i] || diag1[row + i] || diag2[row - i + n]) {
            continue;  // 剪枝
        }
        
        path[row] = i;
        col[i] = diag1[row + i] = diag2[row - i + n] = true;
        dfs(row + 1);
        col[i] = diag1[row + i] = diag2[row - i + n] = false;
    }
}

int main() {
    cin >> n;
    dfs(0);
    cout << count << endl;
    return 0;
}

2. 洛谷 P1706 全排列问题

12345678910111213141516171819202122#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    
    do {
        for (int i = 0; i < n; i++) {
            printf("%5d", a[i]);
        }
        cout << endl;
    } while (next_permutation(a, a + n));
    
    return 0;
}

3. 洛谷 P1605 迷宫

12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>
using namespace std;

int n, m, t;
int sx, sy, fx, fy;
bool grid[10][10];
bool visited[10][10];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int count = 0;

void dfs(int x, int y) {
    if (x == fx && y == fy) {
        count++;
        return;
    }
    
    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 && !visited[nx][ny] && !grid[nx][ny]) {
            visited[nx][ny] = true;
            dfs(nx, ny);
            visited[nx][ny] = false;
        }
    }
}

int main() {
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;
    
    for (int i = 0; i < t; i++) {
        int x, y;
        cin >> x >> y;
        grid[x][y] = true;
    }
    
    visited[sx][sy] = true;
    dfs(sx, sy);
    
    cout << count << endl;
    return 0;
}

易错点

⚠️ 注意：

1. 剪枝要保证正确性
2. 剪枝的顺序可能影响效率
3. 记忆化剪枝要注意状态表示
4. 剪枝是搜索优化的重要技巧