给定N套元素，找到M套的最小并集 [英] Given N sets of elements, find minimal union of M sets

问题描述

给定一个食谱作为一组食材，我正在尝试寻找构成一周食物的最低食材。这就是上面的问题，其中N为配方数，M = 7。

Given a recipe as a set of ingredients, I am trying to find minimum ingredients that make a week worth of meals. This translates to the above problem, with N as number of recipes and 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，但是我想看看其他方法是否也可以使其达到最佳。

I am looking for high level approaches to solve this. I feel this can be reduced to a BFS, but I want to see if other approaches could also make it optimal.

注意：可能会有多个这样的集合，并且基数。

Note: There might be multiple such sets, with same cardinality.

推荐答案

此问题称为MINIMUM k -UNION，它是 NP困难，如下所示：

This problem is known as MINIMUM k-UNION, and it is NP-hard, as shown here:

• Staal A.Vinterbo（2002年）。 有关硬度的说明 k -歧义问题。 DSG技术报告2002-006。

• Staal A. Vinterbo (2002). A Note on the Hardness of the k-Ambiguity Problem. DSG Technical Report 2002-006.

因此，没有人知道任何可以解决多项式大小的多项式的算法。

So no-one knows any algorithm to solve it that runs in time that's polynomial in the size of the input.

在您的情况下，您可能会乐于接受一个近似的解决方案：即，由少量成分组成的食谱集，但不一定最小的此类收藏。因此，我建议您尝试使用 greedy算法：通过在每个阶段添加最小化并集大小的配方来迭代地构建配方的集合。这是一个朴实的Python实现：

In your case, you would probably be happy to accept an approximate solution: that is, a collection of recipes with a small union of ingredients, but not necessarily the very smallest such collection. So I suggest that you try the greedy algorithm: iteratively build up a collection of recipes by adding at each stage the recipe that minimizes the size of the union. Here's a naïve implementation in 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

这篇关于给定N套元素，找到M套的最小并集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！