算法优化中的剪枝技术详解

算法优化中的剪枝技术详解

引用

CSDN

1.

https://blog.csdn.net/2203_76003626/article/details/145357936

剪枝与优化

剪枝，形象地说，就是剪掉搜索树的分支，从而减小搜索树的规模，排除掉搜索树中没有必要的分支，优化时间复杂度。在深度优先遍历中，有几种常见的剪枝方法：

1. 排除等效冗余：如果在搜索过程中，通过某一个节点往下的若干分支中，存在最终结果等效的分支，那么就只需要搜索其中一条分支。
2. 可行性剪枝：如果在搜索过程中，发现有一条分支是无论如何都拿不到最终解，此时就可以放弃这个分支，转而搜索其它的分支。
3. 最优性剪枝：在最优化的问题中，如果在搜索过程中，发现某一个分支已经超过当前已经搜索过的最优解，那么这个分支往后的搜索，必定不会拿到最优解。此时应该停止搜索，转而搜索其它情况。
4. 优化搜索顺序：在有些搜索问题中，搜索顺序是不影响最终结果的，此时搜索顺序的不同会影响搜索树的规模。因此，应当先选择一个搜索分支规模较小的搜索顺序，快速拿到一个最优解之后，用最优性剪枝剪掉别的分支。
5. 记忆化搜索：记录每一个状态的搜索结果，当下一次搜索到这个状态时，直接找到之前记录过的搜索结果。记忆化搜索，有时也叫动态规划。

1. 数的划分

P1025 [NOIP2001 提高组] 数的划分

解法：剪枝与优化

搜索策略：

1. 将 [1, n] 个数放在 k 个坑里面，使的坑里面的所有数的总和是 n。
2. 其中，不同的坑里面的数可能相同。
3. 但是 [1, 2] 与 [2, 1] 是同一种分法，因此，应该是一种组合型枚举。针对每一个坑里面的数应该放谁的时候，应该从上一个坑里面的数开始枚举。

剪枝策略：当我们填了 cnt 个坑时，此时总和是 sum，如果后续坑位全部都填上最小值都会超过 n。说明我们之前填的数太大了，导致后面怎么填都会超过 n，直接剪掉。

注意：剪枝位置的不同，而导致搜索树的不同：

1. 如果在进入递归之前剪枝，我们不会进入不合法的递归函数中。
2. 但是如果在进入递归之后剪枝，我们就会多进⼊很多不合法的递归函数中。

#include<iostream>
#include<vector>
using namespace std;
int n, k;
vector<int> path;
int sum;
int ret;
void dfs(int pos)
{
    if(path.size() == k)
    {
        if(sum == n) ret++;
        return;
    }
    //if(sum + pos * (k - path.size()) > n) return; //放在这里会超时
    
    for(int i = pos; i <= n; i++)
    {
        if(sum + i * (k - path.size()) > n) return; //可行性剪枝
        
        path.push_back(i);
        sum += i;
        dfs(i);
        
        //回溯：恢复现场
        sum -= i;
        path.pop_back();
    }
}
int main()
{
    cin >> n >> k;
    dfs(1);
    cout << ret << endl;
    
    return 0;
}

2. 小猫爬山

P10483 小猫爬山

解法：剪枝与优化

搜索策略：依次处理每一只猫，对于每一只猫，我们都有两种处理方式：

1. 要么把这只猫放在已经租好的缆车上。
2. 要么重新租一个缆车，把这只猫放上去。

剪枝：

1. 在搜索过程中，我们用全局变量记录已经搜索出来的最小缆车数量。如果当前搜索过程中，已经用的缆车数量大于全局记录的最小缆车数量，那么这个分支一定不会得到最优解，剪掉。
2. 优化枚举顺序一：从大到小安排每一只猫

• 重量较大的猫能够快速把缆车填满，较快得到一个最小值。
• 通过这个最小值，能够提前把分支较大的情况提前剪掉。

1. 优化枚举策略二：先考虑把小猫放在已有的缆车上，然后考虑重新租一辆车。如果反着来，我们会先把缆车较大的情况枚举出来，这样就起不到剪枝的效果了。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int n, w;
int a[N]; //小猫的重量信息
int cnt;   //缆车的数量
int st[N]; //第i个缆车上小猫的总重量
int ret = N; //最优解
//pos: 第pos只小猫
void dfs(int pos)
{
    if(cnt >= ret) return; //最优性剪枝：若缆车的数量大于等于最优解->直接结束
    
    if(pos > n) //递归结束：枚举完所有的小猫->更新最优解
    {
        ret = cnt;
        return;
    }
    
    //优化搜索顺序
    //先在已有的缆车上放置小猫
    for(int i = 1; i <= cnt; i++)
    {
        if(st[i] + a[pos] > w) continue; //可行性剪枝
        
        st[i] += a[pos];
        dfs(pos + 1); //递归下一只小猫
        st[i] -= a[pos]; //回溯：恢复现场
    }
    
    //重新开一辆缆车
    ++cnt;
    st[cnt] = a[pos];
    dfs(pos + 1); //递归下一只小猫
    st[cnt] = 0; //回溯：恢复现场
    --cnt;
}
int main()
{
    cin >> n >> w;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, [&](int a, int b){ return a > b; }); //降序->优化搜索顺序
    dfs(1);
    cout << ret << endl;
    
    return 0;
}