剪枝

逃离我推掉我的手 2023-11-02 06:26 88阅读 0赞

一、剪枝的由来

常用的搜索有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.搜索顺序剪枝**

在一些迷宫题，网格题，或者其他搜索中可以贪心的题，搜索顺序显得十分重要。我经常听见有人说(我自己也说过)：“从左边搜会T，从右边搜就A了”之类的语句。

其实在迷宫、网格类的题目中，以左上->右下为例，右下左上就明显比左上右下优秀。

在一些推断搜索题中，从已知信息最多的地方开始搜索显然更加优秀。

在一些题中，先搜某个值大的，再搜某个值小的(比如树的度数，产生答案的预计(A\*))，速度明显会比乱搜更快。

搜索的复杂度明显讲不清，这种剪枝自然是能加就加。

发表评论取消回复

表情：

评论列表（有 0 条评论，88人围观）

还没有评论，来说两句吧...

相关阅读

相关剪枝

一、剪枝的由来常用的搜索有Dfs和Bfs。 Bfs的剪枝通常就是判重，因为一般Bfs寻找的是步数最少，重复的话必定不会在之前的情况前产生最优解。深搜，它的进程近似一颗

逃离我推掉我的手/ 2023年11月02日 06:26/ 0 赞/ 89 阅读

相关剪枝技巧

1. 剪枝1：常用的指定顺序, 即枚举第i个顶后, 以后再枚举时枝考虑下标比大它的, 避免重复。 2. 剪枝2：自己开始从前往后的枚举顶点, TLE两次. 后来从后往前

不念不忘少年蓝@/ 2023年08月17日 16:26/ 0 赞/ 82 阅读

相关 keras剪枝-量化-推理

tensorflow提供了一个优化工具tensorflow\_model\_optimization ，专门针对keras进行模型优化主要可以进行剪枝、量化和权重聚类这

待我称王封你为后i/ 2023年01月10日 10:19/ 0 赞/ 113 阅读

相关模型剪枝

[https://blog.csdn.net/qq\_38109843/article/details/107234801][https_blog.csdn.net_qq

叁歲伎倆/ 2022年11月16日 13:58/ 0 赞/ 185 阅读

相关奇偶剪枝

这里我来讲一下搜索中要用到的奇偶剪枝的原理： ![1366696322_8124.gif][] 看张图，没障碍物\时，S到E的最短路长为6，但是当有障碍

ゞ浴缸里的玫瑰/ 2022年08月08日 14:52/ 0 赞/ 171 阅读

相关 dfs+剪枝 poj1011

大致题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。思路：对所有的棒子求和sum之后除以4，得到边长side，问题就转换为求这些棒子能否拼接成4个长度为side的

小咪咪/ 2022年08月03日 16:54/ 0 赞/ 144 阅读

相关奇偶剪枝

明天再详细补充。。。百度百科粘过来的 ![20130522221549745][] 奇偶剪枝是数据结构的搜索中，剪枝的一种特殊小技巧。描述现假设起点为(sx,

以你之姓@/ 2022年06月14日 23:11/ 0 赞/ 220 阅读

相关剪枝

将复杂的决策树进行简化的过程称为剪枝，它的目的是去掉一些节点，包括叶节点和中间节点。剪枝常用方法：预剪枝与后剪枝两种。预剪枝：在构建决策树的过程中，提前终止决策树

╰半橙微兮°/ 2022年05月16日 11:26/ 0 赞/ 220 阅读

相关 Luogu P1120 小木棍［数据加强版］来来来我们一起来剪枝，剪枝，剪枝、、、...

好啊。。。太棒了。。。 -------------------- dfs（拼到第几根木棍，这根木棍剩余长度，上一根木棍的位置） len是木棍的长度，cnt是木棍的个数

矫情吗；*/ 2021年11月17日 15:26/ 0 赞/ 253 阅读

相关 CART剪枝

1. CART剪枝介绍 > CART 剪枝算法从完全生长的决策树的底端剪去一些子树，使决策树变小（模型简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成

今天药忘吃喽~/ 2021年09月30日 06:50/ 0 赞/ 276 阅读