搜索剪枝

目录

什么是剪枝

几种常见的剪枝

1.可行性剪枝

2.排除等效冗余

3.最优性剪枝

4.顺序剪枝

5.记忆化

运用实例

1.选数

2.吃奶酪

3.小木棍

---

什么是剪枝

剪枝：通过某种判断，避免一些不必要的遍历过程。搜索的时间复杂度通常很大，通过剪枝对搜索进行优化，可以大大提高程序运行的效率。

几种常见的剪枝

1.可行性剪枝

判断继续搜索是否能得到答案，如果不能，就返回

即：不可行，就返回

2.排除等效冗余

在搜索的几个分支中具有完全相同的效果时，选择其中一个走即可

即：有相同，选一个

3.最优性剪枝

和可行性剪枝有点相似，区别在于继续搜索可能得到答案，但一定不是最优

首先得到最优解：每搜索到一个解，和之前的解做对比，得到最优解

然后最优性剪枝：如果当前搜索到的解已经超过最优解，就返回

即：非最优，就返回

4.顺序剪枝

优化搜索顺序，更快得到解

即：先排序，再搜索

5.记忆化

记录每个状态的搜索结果，在后续搜索过程中检索这个状态，如果重复，就返回

即：有重复，就返回

运用实例

1.选数

（详见洛谷P1036）：从n个整数中选k个整数相加，求和为素数共有多少种

输入：n，k，n个整数

输出：种类数

运用：可行性剪枝

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cmath>
4.  
   #define maxn 25
5.  
   using namespace std;
6.  
    
7.  
   int a[maxn];
8.  
   int ans = 0;
9.  
   int n, k;
10.  
     
11.  
    bool isprime(int m)
12.  
    {
13.  
    for (int i = 2; i <= sqrt(m); i )
14.  
    if (m % i == 0) return false;
15.  
    return true;
16.  
    }
17.  
     
18.  
    void dfs(int start,int count,int sum)//当前第start个数，当前已选数个数，当前已选数和
19.  
    {
20.  
    if(count n-start 1<k)//（可行性剪枝）当前已选数个数 剩余数个数<要选的总数个数k
21.  
    {
22.  
    return;
23.  
    }
24.  
    if (count == k)
25.  
    {
26.  
    if(isprime(sum))
27.  
    ans ;
28.  
     
29.  
    return;//可行性剪枝
30.  
    }
31.  
    for(int i=start;i<=n;i )
32.  
    {
33.  
    dfs(i 1, count 1, sum a[i]);
34.  
    }
35.  
    }
36.  
     
37.  
    int main()
38.  
    {
39.  
    cin >> n >> k;
40.  
    for (int i = 1; i <= n; i )
41.  
    {
42.  
    cin >> a[i];
43.  
    }
44.  
     
45.  
    dfs(1,0,0);
46.  
    cout << ans;
47.  
    }

2.吃奶酪

（详见洛谷P1433）：有n块奶酪，现在要把它们都吃掉，求最短的经过的距离(初始在原点处)

输入：奶酪数量n，每块奶酪的坐标

输出：最少距离（保留两位小数）

运用：可行性剪枝，最优性剪枝，记忆化剪枝

首先只加上可行性剪枝：

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cmath>
4.  
   #include<iomanip>
5.  
   #define maxn 20
6.  
   using namespace std;
7.  
    
8.  
   double ans= 0x3f3f3f3f;
9.  
   int n,visited[maxn];
10.  
     
11.  
    struct POINT
12.  
     
13.  
    {
14.  
    double x, y;
15.  
    }a[maxn];
16.  
     
17.  
     
18.  
    double dis(POINT& a, POINT& b)
19.  
    {
20.  
    return sqrt(pow((a.x - b.x), 2)*1.0 pow((a.y - b.y), 2)*1.0);
21.  
    }
22.  
     
23.  
    void dfs(int now,int count,double sum)//序号,吃掉数量,距离
24.  
    {
25.  
    if (count == n)
26.  
    {
27.  
    ans = min(ans, sum);
28.  
    return;//不可行，返回
29.  
    }
30.  
     
31.  
    for (int i = 1; i <= n; i )
32.  
    {
33.  
    if (!visited[i])
34.  
    {
35.  
    visited[i] = 1;
36.  
    dfs(i, count 1, sum dis(a[now],a[i]));
37.  
    visited[i] = 0;
38.  
    }
39.  
    }
40.  
    }
41.  
     
42.  
    int main()
43.  
    {
44.  
    cin >> n;
45.  
    for (int i = 1; i <= n; i )
46.  
    cin >> a[i].x >> a[i].y;
47.  
    a[0].x = 0;
48.  
    a[0].y = 0;
49.  
    dfs(0,0,0);
50.  
    cout <<fixed<<setprecision(2) << ans;
51.  
    }
52.  
     

只能得到50分

现在加上最优性剪枝：

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cmath>
4.  
   #include<iomanip>
5.  
   #define maxn 20
6.  
   using namespace std;
7.  
    
8.  
   double ans= 0x3f3f3f3f;
9.  
   int n,visited[maxn];
10.  
     
11.  
    struct POINT
12.  
     
13.  
    {
14.  
    double x, y;
15.  
    }a[maxn];
16.  
     
17.  
     
18.  
    double dis(POINT& a, POINT& b)
19.  
    {
20.  
    return sqrt(pow((a.x - b.x), 2)*1.0 pow((a.y - b.y), 2)*1.0);
21.  
    }
22.  
     
23.  
    void dfs(int now,int count,double sum)//序号,吃掉数量,距离
24.  
    {
25.  
    if (sum >= ans)//最优性剪枝
26.  
    return;
27.  
     
28.  
    if (count == n)
29.  
    {
30.  
    ans = min(ans, sum);
31.  
    return;
32.  
    }
33.  
     
34.  
    for (int i = 1; i <= n; i )
35.  
    {
36.  
    if (!visited[i])
37.  
    {
38.  
    visited[i] = 1;
39.  
    dfs(i, count 1, sum dis(a[now],a[i]));
40.  
    visited[i] = 0;
41.  
    }
42.  
    }
43.  
    }
44.  
     
45.  
    int main()
46.  
    {
47.  
    cin >> n;
48.  
    for (int i = 1; i <= n; i )
49.  
    cin >> a[i].x >> a[i].y;
50.  
    a[0].x = 0;
51.  
    a[0].y = 0;
52.  
    dfs(0,0,0);
53.  
    cout <<fixed<<setprecision(2) << ans;
54.  
    }
55.  
     

 什么？竟然还不能通过

那就再加上记忆化剪枝，把每次计算的两点间距离都保存起来，下次遇到直接调用

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cmath>
4.  
   #include<iomanip>
5.  
   #define maxn 20
6.  
   using namespace std;
7.  
    
8.  
   double ans= 0x3f3f3f3f;
9.  
   int n,visited[maxn];
10.  
    double map[maxn][maxn];
11.  
     
12.  
    struct POINT
13.  
     
14.  
    {
15.  
    double x, y;
16.  
    }a[maxn];
17.  
     
18.  
     
19.  
    double dis(POINT& a, POINT& b)
20.  
    {
21.  
    return sqrt(pow((a.x - b.x), 2)*1.0 pow((a.y - b.y), 2)*1.0);
22.  
    }
23.  
     
24.  
    void dfs(int now,int count,double sum)//序号,吃掉数量,距离
25.  
    {
26.  
    if (sum >= ans)//最优性剪枝
27.  
    return;
28.  
     
29.  
    if (count == n)
30.  
    {
31.  
    ans = min(ans, sum);
32.  
    return;
33.  
    }
34.  
     
35.  
    for (int i = 1; i <= n; i )
36.  
    {
37.  
    if (!visited[i])
38.  
    {
39.  
    if (map[now][i])//记忆化，提取之前记录过的距离
40.  
    {
41.  
    visited[i] = 1;
42.  
    dfs(i, count 1, sum map[now][i]);
43.  
    visited[i] = 0;
44.  
    }
45.  
    else
46.  
    {
47.  
    map[now][i] = dis(a[now], a[i]);//记忆
48.  
    visited[i] = 1;
49.  
    dfs(i, count 1, sum map[now][i]);
50.  
    visited[i] = 0;
51.  
    }
52.  
    }
53.  
    }
54.  
    }
55.  
     
56.  
    int main()
57.  
    {
58.  
    cin >> n;
59.  
    for (int i = 1; i <= n; i )
60.  
    cin >> a[i].x >> a[i].y;
61.  
    a[0].x = 0;
62.  
    a[0].y = 0;
63.  
    dfs(0,0,0);
64.  
    cout <<fixed<<setprecision(2) << ans;
65.  
    }

 恭喜，看来这道题不用dp是通过不了了的，然而我还不会dp，等以后再来解决吧

3.小木棍

（详见洛谷P1120）：有一些同样长的木棍被随意砍成几段，求原始木棍的最小可能长度

输入：分段后的小木棍个数n，每个小木棍的长度

输出：最小可能的长度

运用：可行性剪枝，最优性剪枝，顺序剪枝

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cmath>
4.  
   #include<cstring>
5.  
   using namespace std;
6.  
    
7.  
   int n;
8.  
   int a[110];
9.  
    
10.  
    int maxm = 0, minm = 51;//小木棍最长长度，最短长度
11.  
    int ans;//当前成功拼接的木棍数
12.  
    int p = 0;//木棍总长度
13.  
     
14.  
    void dfs(int x, int y, int z)//x:每根木棍期望长度，y：现在拼成长度，z：上一次使用的木棍长度
15.  
    {
16.  
    if (ans * x == p)
17.  
    {
18.  
    cout << x;
19.  
    exit(0);//（最优性剪枝）
20.  
    }
21.  
    for (int i = z; i >= minm; i--)//从最长的小木棍开始拼（顺序剪枝）
22.  
    {
23.  
    if (a[i] && y i <= x)//长度为a[i]的木棍拼接起来不会超过期望长度
24.  
    {
25.  
    y = i;
26.  
    a[i]--;
27.  
    if (y == x)
28.  
    ans , y = 0;//拼接成功
29.  
     
30.  
    if (y == 0)
31.  
    dfs(x, y, maxm);//搜索下一个木棍
32.  
    else
33.  
    dfs(x, y, i);//搜索下一个小木棍
34.  
     
35.  
    //回溯
36.  
    a[i] ;
37.  
    if (ans > 0 && y == 0)y = x - i,ans--;
38.  
    else y -= i;
39.  
     
40.  
    if (y == 0) break;//拼接没有成功，返回（可行性剪枝）
41.  
    if (y i == x)break;//到达上一根木棍拼接状态，返回
42.  
    }
43.  
    }
44.  
    }
45.  
     
46.  
    int main()
47.  
    {
48.  
    cin >> n;
49.  
     
50.  
    for (int i = 1; i <= n; i )
51.  
    {
52.  
    int temp;
53.  
    cin >> temp;
54.  
    if (temp <= 50)
55.  
    {
56.  
    a[temp] ;//长度为temp的木棍数量 1
57.  
    p = temp;
58.  
    maxm = max(temp, maxm);
59.  
    minm = min(temp, minm);
60.  
    }
61.  
    }
62.  
    for (int i = maxm; i <= p / 2; i )//小木棍木棍最长长度->总长度的一半
63.  
    {
64.  
    //木棍总长度也就是原始木棍长度一定能够整除单个木棍长度
65.  
    if(p%i==0)
66.  
    {
67.  
    ans = 0;
68.  
    dfs(i, 0, maxm);//期望长度=i,现在拼成长度=0,使用长度=maxm
69.  
    }
70.  
    }
71.  
     
72.  
    cout << p;//搜索不成功，全部拼成1根
73.  
     
74.  
    }
75.  
     

这篇好文章是转载于：学新通技术网