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了,不需要再去尝试找其他的方案了,所以应立即返回.