给定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,如下所示:

• 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