剪枝形象得看就是剪掉搜索树的分⽀从⽽减⼩搜索树的规模排除掉搜索树中没有必要的分⽀优化时间复杂度。在深度优先遍历中有⼏种常⻅的剪枝⽅法排除等效冗余如果在搜索过程中通过某⼀个节点往下的若⼲分⽀中存在最终结果等效的分⽀那么就只需要搜索其中⼀条分⽀。可⾏性剪枝如果在搜索过程中发现有⼀条分⽀是⽆论如何都拿不到最终解此时就可以放弃这个分⽀转⽽搜索其它的分⽀。最优性剪枝在最优化的问题中如果在搜索过程中发现某⼀个分⽀已经超过当前已经搜索过的最优解那么这个分⽀往后的搜索必定不会拿到最优解。此时应该停⽌搜索转⽽搜索其它情况。优化搜索顺序在有些搜索问题中搜索顺序是不影响最终结果的此时搜索顺序的不同会影响搜索树的规模。因此应当先选择⼀个搜索分⽀规模较⼩的搜索顺序快速拿到⼀个最优解之后⽤最优性剪枝剪掉别的分⽀。记忆化搜索记录每⼀个状态的搜索结果当下⼀次搜索到这个状态时直接找到之前记录过的搜索结果。记忆化搜索有时也叫动态规划。第一第二条在之前的DFS例题中经常出现这篇主要介绍一下第三条和第四条1.P1025 [NOIP 2001 提高组] 数的划分解题思路当我们填了pos 个坑时此时总和是sum 如果后续坑位全部都填上最⼩值都会超过sum 。说明我们之前填的数太⼤了导致后⾯怎么填都会超过sum 直接剪掉。#includeiostreamusingnamespacestd;intn,k;intret;intpath;voiddfs(intpos,intbegin){if(posk){if(pathn){ret;}return;}//下次进入循环才能判断//if ((n - path) (k - pos) * begin)//{// return;//}for(intibegin;in;i){//未进入循环就可以判断if((n-path)(k-pos)*i){return;}pathi;dfs(pos1,i);path-i;}}intmain(){cinnk;dfs(0,1);coutret;}注意• 如果在进⼊递归之前剪枝我们不会进⼊⾮法的递归函数中• 但是如果在进⼊递归之后剪枝我们就会多进⼊很多不合法的递归函数中。这里的dfs(0,1)从0开始是因为我们的判断条件在for循环里面比如进入dfs(0,3) ,判断时n - path) (k - pos) *i 这里的k-pos应该是3如果改成1,1则会判断错误1.2P10483 小猫爬山解题思路要加入一只小猫时先判断目前已有的车是否可以加上小猫而且不超重不行的话再单开一辆车。• 优化枚举顺序⼀从⼤到⼩安排每⼀只猫重量较⼤的猫能够快速把缆⻋填满较快得到⼀个最⼩值通过这个最⼩值能够提前把分⽀较⼤的情况提前剪掉。• 优化枚举策略⼆先考虑把⼩猫放在已有的缆⻋上然后考虑重新租⼀辆⻋因为如果反着来我们会先把缆⻋较⼤的情况枚举出来这样就起不到剪枝的效果了。#includeiostream#includealgorithmusingnamespacestd;intn,k,cnt,path;constintN20;inta[N];ints[N];intretN;boolcmp(inta,intb){returnab;}voiddfs(intpos){//最优性剪枝if(cntret)return;if(posn){retcnt;return;}// 策略三优化搜索顺序// 先安排在已有的⻋辆上for(inti1;icnt;i){// 策略⼀可⾏性剪枝if((s[i]a[pos])k)continue;s[i]a[pos];dfs(pos1);s[i]-a[pos];}cnt;s[cnt]a[pos];dfs(pos1);s[cnt]0;cnt--;}intmain(){cinnk;for(inti1;in;i){cina[i];}// 策略三优化搜索顺序sort(a1,a1n,cmp);dfs(1);coutret;}