• 注册
当前位置:1313e > 默认分类 >正文

剪枝技巧

 

1. 剪枝1:常用的指定顺序, 即枚举第i个顶后, 以后再枚举时枝考虑下标比大它的, 避免重复。

2. 剪枝2:自己开始从前往后的枚举顶点, TLE两次. 后来从后往前枚举顶点,发现可以利用顶点之间的承袭性.我用num[i] 记录的可选顶点集合为 V[i, i+1, ... , n] 中的最大团数目, 目标是求num[1].

     分析易知, num[i] = num[i+1] 或者 num[i]+1   (num[1...n] 具有非降的单调性,从后往前求)

     由这个式子以及num[]信息的记录,使得我们可以增加两处剪枝:

3.上/下剪枝:假设当前枚举的是顶点x, 它的第一个邻接顶是i (标号一定比x大,即num[i]已经求出) 我们可以知道, 若 1 + num[i] <= best, 那么是没没要往下枚举这个顶点x了,因为包含它的团是不可能超过我们目前的最优值的。

4. 立即返回剪枝: 由于num[i]最大可能为num[i+1]+1, 所以在枚举顶点i时,只要一更新best,可知此时的num[i]就为num[i+1]+1了,不需要再去尝试找其他的方案了,所以应立即返回.

转载于:https://www.cnblogs.com/Aiahtwo/p/11437050.html

本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 162202241@qq.com 举报,一经查实,本站将立刻删除。

最新评论

欢迎您发表评论:

请登录之后再进行评论

登录