Dados N conjuntos de elementos, encuentre una unión mínima de conjuntos M

Question

Dada una receta como un conjunto de ingredientes, estoy tratando de encontrar los ingredientes mínimos que hacen que una semana valga la pena. Esto se traduce en el problema anterior, con N como número de recetas y 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}. 

Estoy buscando enfoques de alto nivel para resolver esto. Siento que esto se puede reducir a un BFS, pero quiero ver si otros enfoques también podrían hacerlo óptimo.

Nota: Puede haber múltiples conjuntos de este tipo, con la misma cardinalidad.

Answer 1

Este problema se conoce como MÍNIMO k -Union, y es NP-hard, como se muestra aquí:

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

Así que nadie sabe ningún algoritmo para resolverlo que se ejecute en el tiempo que es polinomial en el tamaño de la entrada.

En su caso, probablemente acepte una solución aproximada: es decir, una colección de recetas con una pequeña unión de ingredientes, pero no necesariamente la colección más pequeña. Por lo tanto, le sugiero que pruebe el codicioso algoritmo: crear iterativamente una colección de recetas agregando en cada etapa la receta que minimiza el tamaño de la unión. He aquí una aplicación ingenua en 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