深搜的剪枝策略

2019-04-11

可行性剪枝

搜索过程中，一旦发现某些状态无论如何都不能找到最终解，就可以将其“剪枝”了

从1 ~ 30 选出8个数，使得和值为200

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s) {//i: 数组索引位置； cnt: 以选数据个数; s: 和
    if (cnt > k) {  //可行性剪枝，选择数的个数不可能超过k
		return;
    }
    if (s > sum) {  //可行性剪枝,s大于sum的不用考虑
        return;
    }
    if (i == n) {
        if (cnt == k && s == sum) {
            ans++;
        }
        return;
    }
    dfs(i + 1, cnt, s);  //不选第i个数
    dfs(i + 1, cnt + 1, s + a[i]);  //选第i个数
}
int main() {
    n = 30;
    k = 8;
    sum = 200;
    for (int i = 0; i < 30; i++) {
        a[i] = i + 1;
    }
    ans = 0;
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

最优性剪枝

最优解问题，通常可以用最优性剪枝，如在求解迷宫最短路的时候，若发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的

在搜索是否有可行解的过程中，一旦找到了一组可行解，后面的搜索都不必再进行了，（最优性剪枝的特例）

#include <iostream>
#include <string>
using namespace std;

int n, m;
string mp[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const int INF = 0x3f3f3f3f;
int ans = INF;

bool in(int x, int y)
{
    return 0 <= x && x < n && 0 <= y && y < m;
}

void dfs(int x, int y, int step)
{
    if (step > ans)
    { //不可能再是最优解，不用再算了
        return;
    }
    if (mp[x][y] == 'T')
    {
        ans = step;
        return;
    }
    vis[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && mp[tx][ty] != '*' && !vis[tx][ty])
        {
            dfs(tx, ty, step + 1);
        }
    }
    vis[x][y] = false;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> mp[i];
    }
    int x, y;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 'S')
            {
                x = i, y = j;
            }
        }
    }
    dfs(x, y, 0);
    cout << ans << endl;
}

重复性剪枝

对于某一些特定的搜索方式，一个方案可能会被搜索很多次，这样是没必要的。

给定 n 个整数，要求选出 K 个数，使得选出来的 K 个数的和为 sum。

那么 1, 2, 3这个选取方法能被搜索到 6 次，这是没必要的，因为我们只关注选出来的数的和，而根本不会关注选出来的数的顺序，所以这里可以用重复性剪枝。

我们规定选出来的数的位置是递增的，在搜索的时候，用一个参数来记录上一次选取的数的位置，那么此次选择我们从这个数之后开始选取，这样最后选出来的方案就不会重复了。

当然，搜索的效率也要比直接二进制枚举更高。

void dfs(int s, int cnt, int pos) {
    ...
    ...
    for (int i = pos; i <= n; i++) {
        if (!xuan[i]) {
            xuan[i] = true;
            dfs(s + a[i], cnt + 1, i + 1); // i + 1 表示从上一次选取的位置后面开始选
            xuan[i] = false;
        }
    }
}

奇偶性剪枝

有一个 n×m 大小的迷宫。其中字符'S'表示起点，字符'D'表示出口，字符'X'表示墙壁，字符'.'表示平地。你需要从'S'出发走到'D'，每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。每次移动消耗 1 时间，走过路都会塌陷，因此不能走回头路或者原地不动。现在已知出口的大门会在 T 时间打开，判断在 0 时间从起点出发能否逃离迷宫。
数据范围 n*,m≤10,*T≤50。

我们只需要用DFS来搜索每条路线，并且只需搜到 T 时间就可以了（这是一个可行性剪枝）。但是仅仅这样也无法通过本题，还需考虑更多的剪枝。如上图所示，将 n×m 的网格染成黑白两色。我们记每个格子的行数和列数之和为 x，如果 x 为偶数，那么格子就是白色，反之奇数时为黑色。容易发现相邻的两个格子的颜色肯定不一样，也就是说每走一步颜色都会不一样。更普遍的结论是：走奇数步会改变颜色，走偶数步颜色不变。
那么如果起点和终点的颜色一样，而 T 是奇数的话，就不可能逃离迷宫。同理，如果起点和终点的颜色不一样，而 T 是偶数的话，也不能逃离迷宫。遇到这两种情况时，就不用进行DFS了，直接输出"NO"。
这样的剪枝就是奇偶性剪枝，本质上也属于可行性剪枝。

#include <iostream>
#include <string>
using namespace std;
const int N = 10;
int n, m, T;
string mp[N];
bool vis[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
bool ok;

//x, y 坐标； t 时间
void dfs(int x, int y, int t) {
    if (ok) return; //最优性剪枝
    if (t == T) {   
        if (mp[x][y] == 'D') ok = true;
        return;   //可行性剪枝
    }
    vis[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (0 <= tx && tx < n && 0 <= ty && ty < m && mp[tx][ty] != 'X' && !vis[tx][ty]) {
            dfs(tx, ty, t + 1);
        }
    }

    vis[x][y] = false;
}

int main() {
    cin >> n >> m >> T;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
    }
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 'S')
                sx = i, sy = j;
            if (mp[i][j] == 'D')
                ex = i, ey = j;
        }
    }
    if ((sx + sy + ex + ey + T) % 2 != 0) { //奇偶性剪枝
        cout << "NO" << endl;
    } else {
        ok = false;
        dfs(sx, sy, 0);
        if (ok) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

剪枝例题

引爆炸弹

在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。数据范围：1≤n,m≤1000；

#include <iostream>
using namespace std;

int n, m;
char mp[1000][1000];
bool row[1010], col[1010]; //标记行和列是否被访问过
void dfs(int x, int y) {
    mp[x][y] = '0';
    if (!row[x]) {
        row[x] = true; // 若该行没有被访问过，则这次引爆该行
        for (int i = 0; i < m; i++) {
            if (mp[x][i] == '1') {
                dfs(x, i);
            }
        }
    }
    if (!col[y]) {
        col[y] = true; // 若该列没有被访问过，则这次引爆该列
        for (int i = 0; i < n; i++) {
            if (mp[i][y] == '1') {
                dfs(i, y);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == '1') {
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt << endl;
}

找数字 - (抽象dfs + 剪枝)

给一个数 n，让你找出一个只由 0,1 组成的十进制数 m*，要求这个正整数 m 可以被 n* 整除。输入格式：输入一个整数 n (1≤n<200)。输出格式：对于输入整数 n 的每一个值，输出 m 的相应值，保证有一个数字长度小于 19 位的数字。如果有一个给定值 n 有多个解，其中任何一个都是可以接受的。本题答案不唯一，符合要求的答案均正确样例输入复制：
2
样例输出复制：
10

2分支dfs,要么后面加0，要么后面加1
特别注意不是所有分支都有结果，所以要剪枝
注意条件保证有结果长度小于19，所以当长度大于等于19,return

#include <iostream>
using namespace std;
int n;
bool ok;
void dfs(long long s, int cnt) {
    if (ok) return;   //最优性剪枝，已经找到了可行解，没有必要继续搜索
    if (cnt >= 19) {  //递归出口1，字符串长度超过19
        return;
    }
    if (s % n == 0) { //递归出口2,找到了可行性答案
        ok = true;
        cout << s << endl;
        return;
    }
    dfs(s * 10, cnt + 1);
    dfs(s * 10 + 1, cnt + 1);
}
int main() {
    cin >> n;
    dfs(1, 0); //因为是正整数，故不能为0
    return 0;
}

全排列

从 n 个不同元素中任取 m (m≤n) 个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当m=n 时所有的排列情况叫全排列。今天这道题目很简单就是给你一个整数n ，计算 [1,n] 所有数字的排列组合。输入格式：第一行输入一个整数 n(1≤n≤9). 输出格式：第一行输出一个全排列的方案总数 m。接下来按照字典序依次输出这 m 个排列。排列的字典的比较方法和字符串一样，比如两个排列 a,b，从第一个数开始，找到第一个不同的数的位置为 ii，然后比较 a[i] 和 b[i] 的大小，如果 a[i] 小的，那么 a 的字典序就小，否则 b 的字典序更小。样例输入1:
2
样例输出1
2
12
21

也可以用 next_permutation() 来做

#include <iostream>
#include <set>
#include <string>
using namespace std;
//--------

int n;
bool vis[10];
//n个位置，从1~n中选一个数塞进去，
void dfs(int num, int cnt) {
    if (cnt == n) {
        cout << num << endl;
        return; //小心别少啦！
    }
    for (int i = 1; i <= n; i++) { //对于每一个位置，去枚举每一个可以用的数
        if (!vis[i]) { //如果之前没有被用过
            vis[i] = true; //标记使用该数
            dfs(num * 10 + i, cnt + 1); //对于这种全是数字的用，当成数字拼接好了
            vis[i] = false; //去试探别的数前，要取消对该数的标记
        }
    }
}

int main() {
    cin >> n;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
    }
    cout << ans << endl;
    dfs(0, 0);
    return 0;
}

蒜头君的旅游计划

马上就要放寒假了，蒜头君已经辛勤的工作一年了，打算和家人一起出去旅游放松放松。有经验的人一定知道，出去旅游前一定要有详细的旅行规划。蒜头君打算旅游 n 个城市，但并不是每条路线的花费都是一样的。蒜头君是一个勤俭节俭的人，他就在想怎么把所有的城市旅游一遍花费最小呢？（蒜头君不喜欢重复旅游同一个城市，也就是说已到达过的城市蒜头君是不会再次光临的）
输入格式
第一行输入一个整数 n(1≤n≤15)，表示有 n 个城市。
接下来有一个 n×n 的矩形，表示每两个城市之间的火车花费，每两个城市之间的花费不会超过 10000。
输出格式
输出一个整数，表示从 11 号城市把所有景点旅游一遍并且回到 11 号城市的最小花费。
样例输入
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
样例输出
8

#include <iostream>
#include <algorithm>
using namespace std;
int G[20][20];
bool vis[20];
int n, ans = 0x3f3f3f;
// u:当前所在点   cnt:所走步数    sum：总花费
void dfs(int u, int cnt, int sum) {
    if (sum > ans) { //最优性剪枝
        return;
    }
    if (cnt == n - 1) {
        ans = min(ans, sum + G[u][0]);
    }
    vis[u] = true; //标记在循环外，包含源点，循环n-1次，到达目的
    for (int i = 0; i < n; i++) {
        if(!vis[i]) {
            dfs(i, cnt + 1, sum + G[u][i]);
        }
    }
    vis[u] = false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> G[i][j];
        }
    }
    dfs(0, 0, 0);
    cout << ans;
    return 0;
}

蒜头君手上有一些小木棍，它们长短不一，蒜头君想用这些木棍拼出一个正方形，并且每根木棍都要用到。例如，蒜头君手上有长度为 1，2，3，3, 3 的 5 根木棍，他可以让长度为1，2 的木棍组成一条边，另外三根分别组成 3 条边，拼成一个边长为 3 的正方形。蒜头君希望你提前告诉他能不能拼出来，免得白费功夫。
输入格式
首先输入一个整数 n(4≤n≤20)，表示木棍数量，接下来输入 n 根木棍的长度 pi(1≤pi≤10000)。
输出格式
如果蒜头君能拼出正方形，输出"Yes"，否则输出"No"。
样例输入1复
4
1 1 1 1
样例输出1复
Yes
样例输入2
5
10 20 30 40 50
样例输出2
No

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

int p[25];
bool vis[25];
int n;
int sum = 0;
bool ok;

void dfs(int s, int cnt, int pos) {
    if (ok) { //最优性剪枝
        return;
    }
    if (s > sum / 4) { //注意这里是sum / 4, 别写成 sum % 4
        return;
    }
    if (s == sum / 4) {
        dfs(0, cnt + 1, 0); //pos 重新从0开始搜素
        return;
    }
    if (cnt == 4) {
        ok = true;
        return;
    }
    for (int i = pos; i < n; i++) { //重复性剪枝
        if (!vis[i]) {
            vis[i] = true;  //虽然使用重复性剪枝，但是重新搜索时 pos 从0开始
            dfs(s + p[i], cnt, i + 1);
            vis[i] = false;
        }
    }
}

int main() {
    cin >> n; 
    
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        sum += p[i];
    }
    if (sum % 4 != 0) {
        cout << "No" << endl;
    } else {
        dfs(0, 0, 0);
        if (ok) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}