搜索剪枝技巧
标签: 机试攻略 - 高分篇
学习人数: 14.4k


高清播放
赞赏支持

什么是剪枝?

常用的搜索有DFS和BFS。
BFS的剪枝通常就是判重,因为一般BFS寻找的是步数最少,重复的话必定不会在之前的情况前产生最优解。

 

深搜,它的进程近似一颗树(通常叫DFS树)。
而剪枝就是一种生动的比喻:把不会产生答案的,或不必要的枝条“剪掉”。

 

剪枝的关键就在于剪枝的判断:什么枝该剪,什么枝不该剪,在什么地方减。

 

剪枝的原则?

正确性,准确性,高效性。
常用的剪枝有:可行性剪枝、最优性剪枝、记忆化搜索、搜索顺序剪枝。

1.可行性剪枝

如果当前条件不合法就不再继续搜索,直接return。这是非常好理解的剪枝,搜索初学者都能轻松地掌握,而且也很好想。一般的搜索都会加上。

 

一般格式:

dfs(int x)  
{  
    if(x>n)return;  
    if(!check1(x))return;  
    ....  
    return;  
}  

 

2.最优性剪枝

如果当前条件所创造出的答案必定比之前的答案大,那么剩下的搜索就毫无必要,甚至可以剪掉。
我们利用某个函数估计出此时条件下答案的‘下界’,将它与已经推出的答案相比,如果不比当前答案小,就可以剪掉。

 

一般格式:

long long ans=987474477434487ll;  
... Dfs(int x,...)  
{  
    if(x... && ...){ans=....;return ...;}  
    if(check2(x)>=ans)return ...;    //最优性剪枝   
    for(int i=1;...;++i)  
    {  
        vis[...]=1;   
        dfs(...);  
        vis[...]=0;  
    }  
}  
//一般实现:在搜索取和最大值时,如果后面的全部取最大仍然不比当前答案大就可以返回。  
//在搜和最小时同理,可以预处理后缀最大/最小和进行快速查询。  

 

3.记忆化搜索

记忆化搜索其实很像动态规划(DP)。

它的关键是:如果对于相同情况下必定答案相同,就可以把这个情况的答案值存储下来,以后再次搜索到这种情况时就可以直接调用。

还有就是不能搜出环来,不能互相依赖。

 

一般格式:

long long ans=987474477434487ll;  
... Dfs(int x,...)  
{  
    if(x... && ...){ans=....;return ...;}  
    if(vis[x]!=0)return f[x];vis[x]=1;  
    for(int i=1;...;++i)  
    {  
        vis[...]=1;   
        dfs(...);  
        vis[...]=0;  
        f[x]=...;  
    }  
}  

 

4.搜索顺序剪枝...

登录查看完整内容


课后作业

掌握搜索剪枝技巧


登录后开始许愿

暂无评论,来抢沙发