搜索 剪枝优化技术
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了搜索 剪枝优化技术,现在分享给大家,供学习和参考。文章包含1012字,纯文字阅读大概需要3分钟。
教程信息
(一)什么是剪枝技术
DFS搜索的时间复杂度通常很大,一般都是指数级的,通常需要优化。
剪枝技术是一种在搜索算法中使用的优化技术,剪枝技术的名字取自“修剪表示解空间的答案树”,可以帮助缩小解空间,从而提高搜索效率。
DFS剪枝技术的核心思想是在不必要的情况下不再继续探索这个节点的子节点,以此减少搜索的深度和广度。
剪枝技术简单的使用if语句即可,复杂的可以单独写一个剪枝判断函数。
(二)几种常见的剪枝思路
1、可行性剪枝
判断继续搜索是否能得到答案,如果不能,就返回。
2、重复性剪枝
在搜索的几个分支中具有完全相同的效果时,选择其中一个走即可。
3、最优性剪枝
求解最优解时,如果当前搜索到的解已经超过最优解的要求,就返回。
4、记忆化剪枝
记录每个结点结果,在后续搜索过程中如果重复搜索到这个结点,就返回(即记忆化搜索)。
(三)一个剪枝的例子
题目来源:
https://www.luogu.com.cn/problem/P1605
题目内容:
实现代码:
#include<bits/stdc++.h> // n代表数字,m代表分拆多少份。 int n, m, ans = 0; void dfs(int k, int s, int last) { // 执行三次求和等同于三次拆分 if (k == m + 1) { // 总和等于n if (s == n) { cout << k << endl; ans++; } return; } // 剪枝1:从结果的重复规律看,后续的结果数字一定大于前面的数字,设置last记录状态服务于剪枝1 // 剪枝2:从后续数字不能大于7-求和的规律看,循环可以缩减到小于等于n-s的范围 for (int i = last; i <= (n-s); i++) { // 递归索引 dfs(k + 1, s + i, i); } } int main() { cin >> n >> m; // 起始广搜 ,从1,0开始。 dfs(1, 0, 1); cout << ans; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供搜索 剪枝优化技术的全部内容,希望教程文章能够帮你了解学习搜索 剪枝优化技术,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-288.html