选取两两不交且覆盖元素最多的集合组合的优于O(2^m)算法

问题描述 #

给定m个集合（m<100），所有集合内元素取值范围为1~n（n<100），需要从给定集合中选取若干个构成组合，满足两个要求：

• 组合内任意两个集合不存在交集
• 组合覆盖的元素总数量最多
  示例：

输入：[{1,2,3},{2,4},{3,5}]
输出：[{2,4},{3,5}]
核心疑问：该问题是否存在时间复杂度优于O(2^m)的求解方案？

解答 #

首先说本质：这个问题就是经典的最大权集合装箱问题，每个集合的权重就是它包含的元素个数，目标是选出两两不交的集合，让总权重最大。
从计算复杂度的分类来说，这个问题属于NP难问题，不存在对任意规模输入都有效的多项式时间解法，但结合题目给出的m<100、n<100的约束，不管是理论复杂度还是实际运行效率，都有远优于O(2^m)的可行方案：

• 转化为最大权独立集求解
  先把问题转成图模型：每个集合对应图上一个顶点，顶点的权重就是对应集合的元素个数；如果两个集合有交集，就在对应的两个顶点之间连一条边。这时候原问题就完全等价于在这个图上找权值和最大的独立集（也就是任意两个选中的顶点之间没有边）。
  针对100个顶点规模的最大权独立集，现在成熟的精确算法搭配分支规约、记忆化搜索、剪枝优化，理论时间复杂度可以做到O(1.19^m)，和O(2m)比差了十几个数量级，普通家用电脑就能秒出结果。
• 基于元素维度的状压DP（适合n远小于m的场景）
  如果n的规模比m小很多（比如n<30），直接用状态压缩DP就行：用二进制数标记当前已经覆盖的元素集合，dp[mask]表示覆盖mask对应的元素时能拿到的最大元素总数，遍历每个集合做类似01背包的转移就可以，时间复杂度是O(m*2^{n)。只要n<27，这个复杂度就比m=100时的O(2}m)（2^{100是根本算不完的天文数字）优得多。如果n在40左右，还可以对元素做折半的meet-in-the-middle优化，复杂度降到O(n*2}{n/2})，依然远好于O(2^m)。
• 带强剪枝的分支定界搜索
  就算n和m都接近100，用分支定界搜索效率也很高：
  • 预处理阶段先做基础剪枝：如果某个集合和其他所有集合都没有交集，直接把它加入最终结果，不用纳入后续搜索；如果有两个集合完全相同，只保留一个，避免重复计算。
  • 搜索时优先选元素个数多、和其他集合交集少的集合做分支，每次计算当前分支的理论上界（当前已经选的元素数+剩余没被冲突的集合最多能贡献的元素数），如果上界都不超过已经搜到的最优值，直接剪掉这个分支，不用往下搜。
    这种方案针对题目给出的规模，实际跑起来速度非常快，复杂度比暴力枚举所有子集的O(2^m)低好几个量级。

拿题目给的示例来说，建图后三个顶点的权重分别是3、2、2，第一个顶点和另外两个都连边（因为第一个集合和后两个都有交集），后两个顶点之间没有边，最大权独立集就是选后两个顶点，总权重4，和示例输出完全一致。

内容的提问来源于stack exchange，提问作者chetir