鉴于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 ķ -union，并且它是NP-hard，如下所示：

• 斯塔尔A. Vinterbo（2002）。 A Note on the Hardness of the k-Ambiguity Problem。 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