剪枝策略

摘要:
修剪,顾名思义,就是通过一些判断来减少搜索树上不必要的子树。有时,我们发现与节点对应的子树的状态不是我们想要的结果,因此我们不需要搜索这个分支。砍倒子树就是修剪。给定可行修剪的n个整数,需要选择K个数,这样所选K个数的和就是和。在搜索时,如果您选择了k个数字,以后再选择更多的数字是没有意义的。所以我们可以直接减去这个搜索分支。例如,如果所有数字都是正数,如果找到当前的和值

剪枝,顾名思义,就是通过一些判断,砍掉搜索树上不必要的子树。有时候,我们会发现某个结点对应的子树的状态都不是我们要的结果,那么我们其实没必要对这个分支进行搜索,砍掉这个子树,就是剪枝。

可行性剪枝

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

在搜索时,如果已经选了k个数,再往后选多的数是没有意义的。所以我们可以直接减去这个搜索分支。

又比如,如果所有的数都是正数,如果一旦发现当前的和值都已经大于sum了,那么之后不管怎么选和值都不可能回到sum了,我们也可以直接终止这个分支的搜索。

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

最优性剪枝

对于求最优解的一类问题,通常可以用最优性剪枝,比如在求解迷宫最短路的时候,如果发现当前的步数已经超过了当前最优解,那从当前状态开始的搜索都是多余的,因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝,可以省去大量冗余的计算。此外,在搜索是否有可行解的过程中,一旦找到了一组可行解,后面所有的搜索都不必再进行了,这算是最优性剪枝的一个特例。

剪枝策略第1张

重复性剪枝

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

再来看这个问题:给定n个整数,要求选出K个数,使得选出来的K个数的和为sum。

如果搜索方法是每次从剩下的数里选一个数,一共搜到第k层,那么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;
        }
    }
}

从1,2,3,4……30这30个数中选取8个数使其和为200

 1 #include <iostream>
 2 using namespace std;
 3 int n, k, sum, ans;
 4 int a[40];
 5 bool xuan[40];
 6 void dfs(int s, int cnt, int pos)//多加一个参数,进行重复性剪枝 
 7 {
 8     if (s > sum || cnt > k) return;//可行性剪枝 
 9 
10     if (s == sum && cnt == k) ans++;
11     for (int i = pos; i < n; i++) 
12     {
13         if (!xuan[i]) 
14         {
15             xuan[i] = 1;
16             dfs(s + a[i], cnt + 1, i + 1);
17             xuan[i] = 0;
18         }
19     }
20 }
21 int main() 
22 {
23     n = 30;
24     k = 8;
25     sum = 200;
26     for (int i = 0; i < 30; i++) 
27         a[i] = i + 1;
28     ans = 0;
29     dfs(0, 0,0);
30     cout << ans << endl;
31     return 0;
32 }
奇偶性剪枝

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

我们只需要用DFS来搜索每条路线,并且只需搜到T时间就可以了(这是一个可行性剪枝)。但是仅仅这样也无法通过本题,还需考虑更多的剪枝。

剪枝策略第2张

如上图所示,将n×m的网格染成黑白两色。我们记每个格子的行数和列数之和x,如果x为偶数,那么格子就是白色,反之奇数时为黑色。容易发现相邻的两个格子的颜色肯定不一样,也就是说每走一步颜色都会不一样。更普遍的结论是:走奇数步会改变颜色,走偶数步颜色不变。

那么如果起点和终点的颜色一样,而T是奇数的话,就不可能逃离迷宫。同理,如果起点和终点的颜色不一样,而T是偶数的话,也不能逃离迷宫。遇到这两种情况时,就不用进行DFS了,直接输出"NO"。

这样的剪枝就是奇偶性剪枝,本质上也属于可行性剪枝。

剪枝条件:(sx + sy + ex + ey + T) % 2 != 0

例题

正方形

剪枝策略第3张

输入样例1

4
1 1 1 1

输出样例1

Yes

输入样例2

5
10 20 30 40 50

输出样例2

No

要一条边一条边地搜索,三条边一起搜索会超时,只需要搜索出前三条边即可。

对于正方形的每一条边,我们能事先计算出长度。

一条边一条边的进行搜索,当搜索到一条边满足长度要求的时候,重新从剩下的木棍中再搜索出一条边,直到搜索出四条边。

像三角形那样同时搜索4条边会超时的。记得需要用重复性剪枝。

ps:三角形那题三条边一起搜的写法

剪枝策略第4张剪枝策略第5张
 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int l[30];
 5 int sum, n;
 6 bool ok;
 7 void dfs(int id, int l1, int l2, int l3) {
 8     if (l1 > sum || l2 > sum || l3 > sum) {
 9         return;
10     }
11     if (ok) {
12         return;
13     }
14     if (id == n) {
15         if (l1 == sum && l2 == sum && l3 == sum) {
16             ok = 1;
17         }
18         return;
19     }
20     dfs(id + 1, l1 + l[id], l2, l3);
21     dfs(id + 1, l1, l2 + l[id], l3);
22     dfs(id + 1, l1, l2, l3 + l[id]);
23 }
24 
25 int main() {
26     freopen("triangle.in", "r", stdin);
27     freopen("triangle.out", "w", stdout);
28     int ca;
29     cin >> n;
30     sum = 0;
31     for (int i = 0; i < n; ++i) {
32         cin >> l[i];
33         sum += l[i];
34     }
35     if (sum % 3) {
36         cout << "no" << endl;
37         return 0;
38     }
39     ok = 0;
40     sum /= 3;
41     dfs(0, 0, 0, 0);
42     if (ok) {
43         cout << "yes" << endl;
44     } else {
45         cout << "no" << endl;
46     }
47     return 0;
48 }
View Code

另外可以提前判断一下,如果所有木棍的和不能被4整除,那么肯定不可能。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const double PI = acos(-1);
17 const double eps =1e-8;
18 #define Bug cout<<"---------------------"<<endl
19 const int maxn=1e5+10;
20 using namespace std;
21 
22 int n,flag;
23 int a[30];//存数据 
24 int vis[30];//判断每条边访问过没 
25 int le[4];//每条边的边长 
26 int L;//标准边长 
27 
28 void DFS(int num,int pos)
29 {
30     if(num>3)//递归出口,已经搜索到了三条边 
31     {
32         flag=1;
33         return ;
34     }
35     if(flag) return ;//最优性剪枝 
36     if(le[num]>L) return ;//可行性剪枝
37     if(le[num]==L) DFS(num+1,1);//找到了一条边
38     else
39     {
40         for(int i=pos;i<=n;i++)
41         {
42             if(vis[i]==0)
43             {
44                 vis[i]=1;
45                 le[num]+=a[i];
46                 DFS(num,i+1);
47                 le[num]-=a[i];
48                 vis[i]=0;
49             }
50         }
51     }
52 }
53 
54 int main()
55 {
56     #ifdef DEBUG
57     freopen("sample.txt","r",stdin);
58     #endif
59     ios_base::sync_with_stdio(false);
60     cin.tie(NULL);
61     
62     scanf("%d",&n);
63     for(int i=1;i<=n;i++)
64     {
65         scanf("%d",&a[i]);
66         L+=a[i];
67     }
68     if(L%4==0)//可以分成4条边 
69     {
70         L/=4;
71         DFS(1,1);
72     }
73     if(flag) printf("Yes
");
74     else printf("No
");
75 
76     return 0;
77 }

免责声明:文章转载自《剪枝策略》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇实现java非阻塞http请求的两种方式Oracle创建视图 及 授权下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Tarjan求割点

概述 在一个无向图中,若删除某个点u后连通分量数目增加,则称点u为该无向图的一个割点(cut vertex) 引理 无向连通图DFS树 从一个节点出发进行DFS,将后访问的结点设为前访问结点的孩子,DFS经过的边叫做DFS树的树边(tree edge),第一次处理时从后代(descendant)指向祖先(ancestor)的边叫做返祖边(back edge...

欧拉回路(fleuru算法实现)

书上的欧拉回路定义不在重复,欧拉回路定义, 弗洛莱走边的方法也不再细讲,弗洛莱算法描述 这里只说怎么进行代码实现。 /* 无向图的欧拉回路 邻接矩阵存图 原理: dfs走边,当走不动时就将其放入栈中,最后将顶点从栈中取出的顺序就是欧拉路径。 如果走错边则必定会堵,那么就会将堵的放入栈中,从栈中取出的话就看作是最后走的割边,符合弗洛来算法; 如果走的...

算法总结—深度优先搜索DFS

深度优先搜索(DFS) 往往利用递归函数实现(隐式地使用栈)。 深度优先从最开始的状态出发,遍历所有可以到达的状态。由此可以对所有的状态进行操作,或列举出所有的状态。 1.poj2386 Lake Couting 题意:八连通被认为连接在一起,求总共有多少个水洼? Sample Input: 10 12 W........WW. .WWW.....WWW...

Java实现 LeetCode 805 数组的均值分割 (DFS+分析题)

805. 数组的均值分割 给定的整数数组 A ,我们要将 A数组 中的每个元素移动到 B数组 或者 C数组中。(B数组和C数组在开始的时候都为空) 返回true ,当且仅当在我们的完成这样的移动后,可使得B数组的平均值和C数组的平均值相等,并且B数组和C数组都不为空。 示例:输入:[1,2,3,4,5,6,7,8]输出: true解释: 我们可以将数组...

codeforces每日一题1-15

目录: 1.1093D. Beautiful Graph(DFS染色) 2.514C - Watto and Mechanism(Tire) 3.69E.Subsegments(STL) 4.25C. Roads in Berland(最短路松弛操作) 5.128B. String Problem (floyd预处理) 6.33C.Wonderful Ra...

图上的文章(割点和桥)

题外话: 今天不想码代码了,知识普及的一天 注意:以下内容是在无向图的基础上 无向图的割点很久之前就知道这些名词 今天终于可以来填坑了。。。 如果将连通图G中的某个点及和这个点相关的边删除后,将使连通分量数量增加,那么这个点就称为图G的割点或是接合点。 如果一个无向图没有割点,则这样的图被称为双连通图。 关于图的割点,有如下两条性质: 【性质一】 如果...