Öğelerin N kümesi verildiğinde, M kümelerinin asgari birleşimini bulun

Question

Bir malzemenin bir tarifi olarak verildiğinde, haftada bir öğün yemek yapmak için en az malzeme bulmaya çalışıyorum. Bu, yukarıdaki soruna, N ile tariflerin sayısı ve M = 7 anlamına gelir.

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

Bunu çözmek için üst düzey yaklaşımlar arıyorum. Bunun bir BFS'ye indirgenebileceğini hissediyorum, ancak diğer yaklaşımların da bunu uygun hale getirip getiremeyeceğini görmek istiyorum.

Not: Aynı kardinaliteye sahip birden fazla set olabilir.

Answer 1

Bu sorun ASGARİ k -Union olarak bilinir ve burada gösterildiği gibi, NP-hard bulunmaktadır:

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

Bu nedenle, hiç kimse, girdinin boyutunda polinom olarak çalışan zamanda çözmek için herhangi bir algoritmayı bilmiyor. Sizin durumunuzda, muhtemelen yaklaşık bir çözümü kabul etmekten mutluluk duyacaksınız: yani, küçük bir malzeme birleşimine sahip bir yemek tarifleri koleksiyonu, ancak mutlaka bu tür en küçük koleksiyonlar olmayabilir. Bu yüzden, açgözlü algoritmasını deneyin: iteratif olarak, her aşamada birliğin boyutunu küçülten reçete ekleyerek bir tarifler koleksiyonu oluşturun. İşte Python bir naif uygulama görebilirsiniz:

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 

Hmm belki Mathforum daha iyi olurdu