《算法竞赛进阶指南》0x23 剪枝

一只野生彩色铅笔

发布于 2022-10-31 11:06:02

4420

发布于 2022-10-31 11:06:02

文章被收录于专栏：彩铅的随笔博客

剪枝基本概念

剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段

形象看，就好像剪掉了搜索树的枝条，故称为剪枝

在深度优先搜索中，有以下几类常见的剪枝手段：

1. 优化搜索顺序

在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的

不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远

比如一个非最优的问题边界，在搜索到最后一层才识别出来舍掉，和搜索到中途就识别出来舍掉，这就是优化搜索顺序的好处

实践出来其实就是：优先搜索那些分支较少的状态

例如：“小猫爬山” 中，小猫的搜索顺序是按照从大到小的例如：“数独” 中，优先搜索 “能填的核发数字” 最少的位置

2. 排除等效冗余

在搜索过程中，如果我们能判定从搜索树的当前结点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索

例如 “数独” 中提出的，初学者一定要避免重叠、混淆 “层次” 与 “分支”，避免遍历若干棵覆盖同一状态空间的等效搜索树

3. 可行性剪枝

在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯

这就好比我们在道路上行走时，看见远方是一个死胡同，就立刻折返绕路，而不是走到尽头再返回

某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为 “上下界剪枝”

4. 最优性剪枝

在最优化问题的搜索过程中，如果当前花费的代价已经超过了当前搜到的最优解，那么无论采取多么优秀的策略到达边界，都不可能更新答案。此时可以停止对当前分支的搜索，执行回溯

5. 记忆化

可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回

这就好比我们对图进行深度优先遍历时，标记一个结点是否已经被访问过

而状态空间是 “树” 的问题，对其用搜索算法遍历，不会重复访问，所有不需要进行记录

习题

木棒

题目描述

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过

个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过

的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于

。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例：

6
5

解析

既然是求可能的最小长度，因此不妨从小到大枚举木棒的初始长度

len

（即枚举答案）

则显然

len

应该是所有木棍的长度总和

sum

的约数，且原始木棒个数为

\dfrac{sum}{len}

对于枚举的每个

len

，我们可以一次搜索每根原始木棒由哪些木棍拼成，所有在搜索过程中，要记录的状态如下：

已经拼好的原始木棒个数

stick

正在拼的原始木棒的当前长度

cur

每个木棍的使用情况

st[\ ]

在每个状态下，我们从尚未使用的木棍中选择一个，尝试拼到当前的原始木棒里，然后递归到新的状态

递归边界就是成功拼好

cnt

个原始木棒，或者因无法继续拼接而宣告失败

在这个搜索的思想上，考虑进行之前提到过的几类剪枝方法：

优化搜索顺序：将木棍按长度从大到小排序，优先尝试较长的木棍

排除等效冗余：

限制先后加入 同一根原始木棒 的木棍长度是递减的这是因为先拼上一根长度为

的木棍，在拼上一个长度为

的木棍（

x<y

），与先拼上

再拼上

是等效的

对于当前原始木棒，记录最近一次尝试拼接的木棍长度，如果分支搜索失败回溯，不再尝试拼接相同长度的木棍
如果在当前原始木棒中 “尝试拼入的第一根木棍” 的递归分支就返回失败，那么直接判定当前搜索分支失败，回溯这是因为拼入这根木棍之前，面对的原始木棒都是“空”的，这些木棒是等效的，因此拼接当前木棍会失败，则当前木棍无论放在后面哪一根木棒搜索里，都会拼接失败
如果在当前原始木棒中拼入一根木棍后，木棒恰好被拼接完整，并且 “接下来拼接剩余原始木棒” 的递归分支返回失败，那么直接判定当前分支失败，回溯该剪枝需要用到贪心思想：“再用一根木棍恰好拼完当前原始木棒” 一定不比 “再用若干根木棍恰好拼完原始木棒” 更差

对于 4 中的贪心思想的证明：

若每一轮木棒搜索中，最后一根木棍

恰好能拼完当前原始木棒时，选择用若干根

x_1,x_2,\cdots,x_i

木棍替代

则在后续搜索中，若搜索成功，木棍

放置的位置，必然可以与

x_1,\cdots,x_i

放置的位置交换，且不会使答案变差

对于 3 中的证明：

若尝试拼入的第一根木棍

没有在当前木棒

stick_{i}

下拼入而是选择了后续的木棒

stick_j

，且方案成功

由于拼好的木棒时等效的，因此不妨交换木棒

stick_{i},\ stick_{j}

又木棒内组成的木棍也是等效的，不妨把

交换到最开头，则显然必定存在一种方案使得

在空木棒的开头搜索成功

上述 1 至 4 分别利用 “同一根木棒上木棍顺序的等效性”、“等长木棍的等效性”、“空木棒的等效性” 和 “贪心” 剪掉了搜索树上的诸多分支，使得搜索效率大大提升

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 70;

int n, len, cnt, sum;
int a[N], st[N];

bool dfs(int stick, int cur, int last)
{
    if (stick == cnt) return true;
    if (cur == len) return dfs(stick + 1, 0, 0);
    
    for (int i = last + 1; i <= n; i ++ )
    {
        if (st[i]) continue;
        if (cur + a[i] > len) continue;
        
        st[i] = true;
        if (dfs(stick, cur + a[i], i)) return true;
        st[i] = false;
        
        if (!cur) return false;                 //(3)
        if (cur + a[i] == len) return false;    //(4)

        int j = i;                              //(2)
        while (j <= n && a[i] == a[j]) j ++ ;
        i = j - 1;
    }
    return false;
}
int main()
{
    while (cin >> n, n)
    {
        sum = len = cnt = 0;
        for (int i = 1; i <= n; i ++ )
        {
            cin >> a[i];
            st[i] = 0;
            sum += a[i];
            len = max(len, a[i]);
        }
        sort(a + 1, a + n + 1); //(1)
        reverse(a + 1, a + n + 1);
        while (true)
        {
            if (sum % len == 0)
            {
                cnt = sum / len;
                if (dfs(0, 0, 0)) break;
            }
            len ++ ;
        }
        printf("%d\n", len);
    }
}

生日蛋糕

题目描述

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为

Nπ

的

层生日蛋糕，每层都是一个圆柱体。

设从下往上数第

层蛋糕是半径为

R_i

，高度为

H_i

的圆柱。

当

i<M

时，要求

R_i>R_{i+1}

且

H_i>H_{i+1}

。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积

最小。

令

Q=Sπ

，请编程对给出的

和

，找出蛋糕的制作方案（适当的

R_i

和

H_i

的值），使

最小。

除

外，以上所有数据皆为正整数。

输入格式

输入包含两行，第一行为整数

，表示待制作的蛋糕的体积为

Nπ

。

第二行为整数

，表示蛋糕的层数为

。

输出格式

输出仅一行，是一个正整数

（若无解则

S=0

）。

数据范围

1≤N≤10000,\ 1≤M≤20

输入样例：

100
2

输出样例：

解析

由题意易得，蛋糕体积和面积公式为：

[ \begin{aligned} \dfrac{V}{\pi} &= R_1^2H_1 + R_2^2H_2 + R_3^2H_3 \cdots + R_m^2H_m = \sum_{i=1}^m R_i^2H_i \\ \dfrac{S}{\pi} &= R_m^2 + 2R_1H_1 + 2R_2H_2 + \cdots + 2R_mH_m = R_m^2 + 2\sum_{i=1}^m R_iH_i \end{aligned} ]

搜索框架：从下往上搜，枚举每层的半径

R_i

和高度

H_i

作为分支

搜索面对的状态有：

正在搜索蛋糕的第

dep

层

当前外表面面积

s\pi

当前体积 v
第

dep + 1

层的高度

h_{dep + 1}

和半径

r_{dep + 1}

整个蛋糕“上表面”面积之和等于最底层的圆面积，可以在第

层直接累加到

中

这样在第

M - 1

层往上搜索时，只需要计算侧面积即可

接下来讨论如何进行剪枝：

上下界剪枝：在第

dep

层时，限制枚举的半径和高度的范围，公式推导：

对于一个总体积为

N\pi

的蛋糕，当前已使用体积为

v\pi

，为使得方案合法显然有上下界限制

下界：由题目定义可知，第

层高和半径至少为

，反推当前层

dep

下界应为：

dep

上界：由题目定义可知，至少要大于第

dep+1

层的半径和高度，于是有：

\begin{cases} R_{dep} \le R_{dep + 1} - 1 \\ H_{dep} \le H_{dep + 1} - 1 \end{cases}

又根据圆柱体体积公式，可得：

N\pi = \pi v + \pi R^2H

根据上述公式，先枚举半径，再用半径推得高度可知：\begin{cases} R_{dep} & ( 1) \ H_{dep} & (RH) \end{cases}

最终确定上下界：

\begin{cases} R_{dep} \in [dep, \min(\lfloor \sqrt{N - v} \rfloor, R_{dep + 1} - 1)] \\ H_{dep} \in [dep, \min(\lfloor \dfrac{N - v}{R^2_{dep}} \rfloor, H_{dep + 1} - 1)] \end{cases}

优化搜索顺序：在上述上下界范围内，倒序枚举

可行性剪枝：

由于第

层半径高度至少为

，也就有了第

层的最小侧面积和体积，不妨预处理出每一层到顶层的最小体积和侧面积

如果当前体积

加上当前层到顶层的最小体积超过了总体积

，则直接剪枝

最优性剪枝：

当前表面积

加上当前层到顶层额最小侧面积超过了已经搜到的答案，则直接剪枝

最优性剪枝二：

1 \sim dep - 1

层的总体积为：

N-v=\sum_{i=1}^{dep-1} R_i^2H_i

，总侧面积为：

S_{1\sim dep-1}=\sum_{i=1}^{dep-1} 2R_iH_i

考虑对

S_{1\sim dep-1}

放缩：

[ S_{1\sim dep-1}=\sum_{i=1}^{dep-1} 2R_iH_i = \frac{2}{R_{dep}} \sum_{i=1}^{dep-1} R_{dep}R_iH_i > \frac{2}{R_{dep}} \sum_{i=1}^{dep-1} R_i^2H_i = \frac{2}{R_{dep}} (N - v) ]

由

S_{1\sim dep-1} > \dfrac{2}{R_{dep}} (N - v)

, 即

S_{1\sim M} = S_{1\sim dep-1} + S_{dep \sim M} > \dfrac{2}{R_{dep}} (N - v) + s

可知，若 S_{1M} 的下界 \(\dfrac{2}{R_{dep}} (N - v) + s\) 已经大于 \(S\) 了，就可以直接剪枝

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 25, INF = 1e9;

int n, m;
int H[N], R[N], S = INF;
int minv[N], mins[N];

void init()
{
    R[m + 1] = H[m + 1] = INF;
    for (int i = 1; i <= m; i ++ )
    {
        mins[i] = mins[i - 1] + 2 * i * i;
        minv[i] = minv[i - 1] + i * i * i;
    }
}
void dfs(int dep, int s, int v)
{
    if (v + minv[dep] > n) return;  //(3)
    if (s + mins[dep] > S)  return; //(4)
    if (s + 2 * (n - v) / R[dep + 1] >= S) return;  //(5)
    if (!dep)
    {
        if (v == n) S = min(S, s);
        return;
    }
    for (int r = min(R[dep + 1] - 1, (int)sqrt(n - v)); r >= dep; r -- ) //(1)&(2)
    {
        for (int h = min(H[dep + 1] - 1, (n - v) / r / r); h >= dep; h -- ) //(1)&(2)
        {
            int tempS = s + 2 * r * h + (dep == m ? r * r : 0);
            int tempV = v + r * r * h;
            R[dep] = r;
            H[dep] = h;
            dfs(dep - 1, tempS, tempV);
        }
    }
}
int main()
{
    cin >> n >> m;
    init();
    dfs(m, 0, 0);
    cout << (S == INF ? 0 : S) << endl;
    return 0;
}

数独2

题目描述

请你将一个

16×16

的数独填写完整，使得每行、每列、每个

4×4

十六宫格内字母

A∼P

均恰好出现一次。

保证每个输入只有唯一解决方案。

输入格式

输入包含多组测试用例。

每组测试用例包括

行，每行一组字符串，共

个字符串。

第

个字符串表示数独的第

行。

字符串包含字符可能为字母 A ∼ P 或 -（表示等待填充）。

测试用例之间用单个空行分隔，输入至文件结尾处终止。

输出格式

对于每个测试用例，均要求保持与输入相同的格式，将填充完成后的数独输出。

每个测试用例输出结束后，输出一个空行。

输入样例：

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-

输出样例：

FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK

解析

只会DLX板子的菜鸡来试图理解深奥的剪枝

加入一下可行性剪枝：

遍历当前所有的空格
1. 若某个位置
A \sim P
都不能填，立即回溯
1. 若某个位置只有
1
个字母可填，立即填上这个字母
考虑所有的行
1. 若某个字母不能填在该行的任何一个空位上，立即回溯
2. 若某个字母只能填在该行的某一个空位上，立即填写
考虑所有的列，执行与第 2 步类似的过程
考虑所有的十六宫格，执行类似的操作

之后，再选择可填的字母最少的位置，枚举填写哪个字母作为分支

本题中如果按照 “数独1” 里的做法，按行/列/九宫格存储所有状态，对于上述的几种剪枝，代码会很复杂

因此考虑对于十六宫格的所有位置存储一个

位的二进制数：

state[i][j]

第

行第

列能填的数字的状态

总共有

16 \times 16 = 256

个二进制状态，将他们备份在一个局部变量上，方便回溯时快速还原

#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int map[1 << N], ones[1 << N];

int state[N][N];
char str[N][N + 1];

int bkstate[N * N + 1][N][N], bk2state[N * N + 1][N][N];
char bkstr[N * N + 1][N][N + 1];


inline int lowbit(int u)
{
    return u & -u;
}
void draw(int x, int y, int t)
{
    str[x][y] = t + 'A';
    for (int i = 0; i < N; i ++ )
    {
        state[i][y] &= ~(1 << t);
        state[x][i] &= ~(1 << t);
    }
    int sx = x / 4 * 4, sy = y / 4 * 4;
    for (int i = 0; i < N / 4; i ++ )
        for (int j = 0; j < N / 4; j ++ )
            state[sx + i][sy + j] &= ~(1 << t);
    state[x][y] = 1 << t;
}
bool remove(int cnt)
{
    memcpy(str, bkstr[cnt], sizeof(str));
    memcpy(state, bkstate[cnt], sizeof(state));
    return false;
}
bool dfs(int cnt)
{
    if (!cnt) return true;

    int kcnt = cnt;
    memcpy(bkstr[kcnt], str, sizeof(str));
    memcpy(bkstate[kcnt], state, sizeof(state));

    //(1.1) & (1.2)
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i][j] == '-' && ones[state[i][j]] == 1) //sole choice
                draw(i, j, map[state[i][j]]), cnt -- ;
            else if (!state[i][j]) return remove(kcnt); //no choice
    //(2)
    for (int i = 0; i < N; i ++ )   //deal row
    {
        int dir_alpha = 0, sole_alpha = (1 << N) - 1;
        int drawn = 0;
        for (int j = 0; j < N; j ++ )
        {
            int s = state[i][j];
            sole_alpha &= ~(dir_alpha & s);
            dir_alpha |= s;
            if (str[i][j] != '-') drawn |= s;
        }
        if (dir_alpha != (1 << N) - 1) return remove(kcnt);
        for (int j = sole_alpha; j; j -= lowbit(j))
        {
            int t = lowbit(j);
            if (drawn & t) continue;
            for (int k = 0; k < N; k ++ )
                if (state[i][k] & t)
                    draw(i, k, map[t]), cnt -- ;
        }
    }
    //(3)
    for (int i = 0; i < N; i ++ )   //deal column
    {
        int dir_alpha = 0, sole_alpha = (1 << N) - 1;
        int drawn = 0;
        for (int j = 0; j < N; j ++ )
        {
            int s = state[j][i];
            sole_alpha &= ~(dir_alpha & s);
            dir_alpha |= s;
            if (str[j][i] != '-') drawn |= s;
        }
        if (dir_alpha != (1 << N) - 1) return remove(kcnt);
        for (int j = sole_alpha; j; j -= lowbit(j))
        {
            int t = lowbit(j);
            if (drawn & t) continue;
            for (int k = 0; k < N; k ++ )
                if (state[k][i] & t)
                    draw(k, i, map[t]), cnt -- ;
        }
    }
    //(4)
    for (int i = 0; i < N; i ++ )
    {
        int dir_alpha = 0, sole_alpha = (1 << N) - 1;
        int drawn = 0;
        for (int j = 0; j < N; j ++ )
        {
            int sx = i / 4 * 4, sy = i % 4 * 4;
            int dx = j / 4, dy = j % 4;
            int s = state[sx + dx][sy + dy];
            sole_alpha &= ~(dir_alpha & s);
            dir_alpha |= s;
            if (str[sx + dx][sy + dy] != '-') drawn |= s;
        }
        if (dir_alpha != (1 << N) - 1) return remove(kcnt);
        for (int j = sole_alpha; j; j -= lowbit(j))
        {
            int t = lowbit(j);
            if (drawn & t) continue;
            for (int k = 0; k < N; k ++ )
            {
                int sx = i / 4 * 4, sy = i % 4 * 4;
                int dx = k / 4, dy = k % 4;
                if (state[sx + dx][sy + dy] & t)
                    draw(sx + dx, sy + dy, map[t]), cnt -- ;
            }
        }
    }

    if (!cnt) return true;
    int s = 100, x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i][j] == '-' && ones[state[i][j]] < s)
                s = ones[state[i][j]], x = i, y = j;
    memcpy(bk2state[kcnt], state, sizeof(state));
    for (int i = state[x][y]; i; i -= lowbit(i))
    {
        memcpy(state, bk2state[kcnt], sizeof(state));
        int t = map[lowbit(i)];
        draw(x, y, t);
        if (dfs(cnt - 1)) return true;
    }
    memcpy(str, bkstr[kcnt], sizeof(str));
    memcpy(state, bkstate[kcnt], sizeof(state));
    return false;
}
int main()
{
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = i; j; j -= lowbit(j))
            ones[i] ++ ;
    while (cin >> str[0])
    {
        for (int i = 1; i < N; i ++ ) cin >> str[i];
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ )
                state[i][j] = (1 << N) - 1;
        int cnt = 0;
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ )
                if (str[i][j] != '-')
                    draw(i, j, str[i][j] - 'A');
                else cnt ++ ;
        dfs(cnt);
        for (int i = 0; i < N; i ++ ) cout << str[i] << endl;
        cout << endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-12，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

搜索

登录后参与评论

0 条评论

热度