鑑於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