e me ocurrió la siguiente implementación para Greedy Set Cover después de mucha discusión sobre mi pregunta originalaqu. De la ayuda que recibí, codifiqué el problema en una "Cubierta de conjunto codicioso" y después de recibir más ayudaaqu, Se me ocurrió la siguiente implementación. Estoy agradecido a todos por ayudarme con esto. La siguiente implementación funciona bien, pero quiero que sea escalable / más rápido.

Por escalable / más rápido, quiero decir que:

Mi conjunto de datos contiene aproximadamente 50K-100K conjuntos en S El número de elementos en U es muy pequeño en el orden de 100-500 El tamaño de cada conjunto en S podría ser de 0 a 40

Y aquí va mi intento:

U = set([1,2,3,4])
R = U
S = [set([1,2]), 
     set([1]), 
     set([1,2,3]), 
     set([1]), 
     set([3,4]), 
     set([4]), 
     set([1,2]), 
     set([3,4]), 
     set([1,2,3,4])]
w = [1, 1, 2, 2, 2, 3, 3, 4, 4]

C = []
costs = []

def findMin(S, R):
    minCost = 99999.0
    minElement = -1
    for i, s in enumerate(S):
        try:
            cost = w[i]/(len(s.intersection(R)))
            if cost < minCost:
                minCost = cost
                minElement = i
        except:
            # Division by zero, ignore
            pass
    return S[minElement], w[minElement]

while len(R) != 0:
    S_i, cost = findMin(S, R)
    C.append(S_i)
    R = R.difference(S_i)
    costs.append(cost)

print "Cover: ", C
print "Total Cost: ", sum(costs), costs

No soy un experto en Python, pero cualquier optimización específica de Python para este código sería realmente buena.