这个问题被称为MINIMUM k -UNIOn,它是NP-hard,如下所示:
- Staal A.Vinterbo(2002年)。关于 k- 歧义问题的难点的一个注记。DSG技术报告2002-006。
因此,没有人知道有什么算法可以解决输入时间为多项式的时间运行算法。
在您的情况下,您可能会乐于接受一个近似的解决方案:即包含少量成分的配方的集合,但不一定是最小的此类集合。因此,我建议您尝试使用 贪婪算法
:通过在每个阶段添加最小化并集的配方来迭代地构建配方集合。这是Python中的一个简单的实现:
def small_union(sets, k): """ Choose `k` elements from `sets` and return their union. Attempt to return a fairly small union using a greedy approach. >>> small_union([{1,2}, {2,3}, {1,2,3}, {1}, {2}], 3) set([1, 2]) >>> small_union([{1,2}, {2,3}, {3,4}, {1,4}], 3) set([1, 2, 3, 4]) """ union = set() for _ in xrange(k): s = min(sets, key = lambda s: len(s | union)) sets.remove(s) union |= s return union
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)