algorithm - 给定 N 组元素，找到 M 组的最小并集

Question

给定一份食谱作为一组配料，我试图找到能做一周饭菜的最低限度的配料。这转化为上述问题，其中 N 为配方数，M = 7。

eg. if the initial sets are [{1,2}, {2,3}, {1,2,3}, {1}, {2}], and M=3
The minimal union is {1,2}.

我正在寻找解决此问题的高级方法。我觉得这可以简化为 BFS，但我想看看其他方法是否也可以使其最佳。

注意：可能有多个这样的集合，具有相同的基数。

Answer 1

这个问题被称为 MINIMUM k -UNION，它是NP-hard，如下所示：

• 斯塔尔 A.温特博 (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