Solución rápida a la sum del subconjunto

Considere esta forma de resolver el problema de la sum del subconjunto:

def subset_summing_to_zero (activities): subsets = {0: []} for (activity, cost) in activities.iteritems(): old_subsets = subsets subsets = {} for (prev_sum, subset) in old_subsets.iteritems(): subsets[prev_sum] = subset new_sum = prev_sum + cost new_subset = subset + [activity] if 0 == new_sum: new_subset.sort() return new_subset else: subsets[new_sum] = new_subset return [] 

Lo tengo desde aquí

http://news.ycombinator.com/item?id=2267392

También hay un comentario que dice que es posible hacerlo “más eficiente”.

¿Cómo?

Además, ¿hay otras formas de resolver el problema que sean al menos tan rápidas como la anterior?

Editar

Estoy interesado en cualquier tipo de idea que conduzca a una aceleración. Encontré:

https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2

que menciona un algoritmo de tiempo lineal. Pero no tengo el periódico, tal vez usted, querida gente, ¿sabe cómo funciona? Una implementación tal vez? Completamente diferente enfoque tal vez?

Editar 2

Ahora hay un seguimiento:
Solución rápida al algoritmo de sum de subconjuntos por Pisinger

Mientras que mi respuesta anterior describe el algoritmo de aproximación de Polytime para este problema, se hizo una solicitud específica para una implementación de la solución de progtwigción dinámica de Polytime de Pisinger cuando todas las x i en x son positivas:

 from bisect import bisect def balsub(X,c): """ Simple impl. of Pisinger's generalization of KP for subset sum problems satisfying xi >= 0, for all xi in X. Returns the state array "st", which may be used to determine if an optimal solution exists to this subproblem of SSP. """ if not X: return False X = sorted(X) n = len(X) b = bisect(X,c) r = X[-1] w_sum = sum(X[:b]) stm1 = {} st = {} for u in range(c-r+1,c+1): stm1[u] = 0 for u in range(c+1,c+r+1): stm1[u] = 1 stm1[w_sum] = b for t in range(b,n+1): for u in range(c-r+1,c+r+1): st[u] = stm1[u] for u in range(c-r+1,c+1): u_tick = u + X[t-1] st[u_tick] = max(st[u_tick],stm1[u]) for u in reversed(range(c+1,c+X[t-1]+1)): for j in reversed(range(stm1[u],st[u])): u_tick = u - X[j-1] st[u_tick] = max(st[u_tick],j) return st 

Wow, eso fue inducir dolor de cabeza. Esto necesita revisión, porque, mientras implementa balsub , no puedo definir el comparador correcto para determinar si existe la solución óptima para este subproblema de SSP.

Respeto la celeridad con la que intentas resolver este problema. Desafortunadamente, está tratando de resolver un problema que es NP-completo , lo que significa que cualquier mejora posterior que rompa la barrera del tiempo polinomial demostrará que P = NP .

La implementación que sacó de Hacker News parece ser consistente con la solución de progtwigción dinámica pseudo-polytime , donde cualquier mejora adicional debe, por definición, avanzar el estado de la investigación actual sobre este problema y todas sus isoformas algorítmicas. En otras palabras: aunque es posible una aceleración constante, es muy poco probable que vea una mejora algorítmica de esta solución al problema en el contexto de este hilo.

Sin embargo, puede usar un algoritmo aproximado si necesita una solución de Polytime con un grado tolerable de error. En pseudocódigo descaradamente robado de Wikipedia, esto sería:

 initialize a list S to contain one element 0. for each i from 1 to N do let T be a list consisting of xi + y, for all y in S let U be the union of T and S sort U make S empty let y be the smallest element of U add y to S for each element z of U in increasing order do //trim the list by eliminating numbers close to one another //and throw out elements greater than s if y + cs/N < z ≤ s, set y = z and add z to S if S contains a number between (1 − c)s and s, output yes, otherwise no 

Implementación de Python, preservando los términos originales lo más cerca posible:

 from bisect import bisect def ssum(X,c,s): """ Simple impl. of the polytime approximate subset sum algorithm Returns True if the subset exists within our given error; False otherwise """ S = [0] N = len(X) for xi in X: T = [xi + y for y in S] U = set().union(T,S) U = sorted(U) # Coercion to list S = [] y = U[0] S.append(y) for z in U: if y + (c*s)/N < z and z <= s: y = z S.append(z) if not c: # For zero error, check equivalence return S[bisect(S,s)-1] == s return bisect(S,(1-c)*s) != bisect(S,s) 

... donde X es su bolsa de términos, c es su precisión (entre 0 y 1), y s es la sum objective.

Para más detalles, mira el artículo de Wikipedia .

( Referencia adicional , lectura adicional en CSTheory.SE )

No sé mucho de Python, pero hay un enfoque llamado meet in the middle. Pseudocódigo:

 Divide activities into two subarrays, A1 and A2 for both A1 and A2, calculate subsets hashes, H1 and H2, the way You do it in Your question. for each (cost, a1) in H1 if(H2.contains(-cost)) return a1 + H2[-cost]; 

Esto le permitirá duplicar la cantidad de elementos de actividades que puede manejar en un tiempo razonable.

Me disculpo por “discutir” el problema, pero un problema de “Suma de Subconjuntos” donde los valores x están acotados no es la versión NP del problema. Las soluciones de progtwigción dinámica son conocidas por problemas de valor x acotado. Esto se hace representando los valores de x como la sum de las longitudes de unidad. Las soluciones de progtwigción dinámica tienen varias iteraciones fundamentales que son lineales con esa longitud total de las x. Sin embargo, la Suma del subconjunto está en NP cuando la precisión de los números es igual a N. Es decir, el número o los valores de lugar de la base 2 necesarios para indicar las x es = N. Para N = 40, las x tienen que estar en los miles de millones. En el problema NP, la longitud de la unidad de las x aumenta exponencialmente con N. Por eso, las soluciones de progtwigción dinámica no son una solución de tiempo polinomial para el problema de sum de subconjuntos NP. Siendo ese el caso, todavía hay instancias prácticas del problema de la sum de subconjuntos donde las x están limitadas y la solución de progtwigción dinámica es válida.

Aquí hay tres maneras de hacer que el código sea más eficiente:

  1. El código almacena una lista de actividades para cada sum parcial. Es más eficiente en términos de memoria y tiempo almacenar solo la actividad más reciente que se necesita para hacer la sum, y ​​resolver el rest retrocediendo una vez que se encuentra una solución.

  2. Para cada actividad, el diccionario se vuelve a llenar con los contenidos anteriores (subconjuntos [prev_sum] = subconjunto). Es más rápido simplemente crecer un solo diccionario

  3. Dividir los valores en dos y aplicar una reunión en el enfoque medio.

La aplicación de las dos primeras optimizaciones da como resultado el siguiente código, que es más de 5 veces más rápido:

 def subset_summing_to_zero2 (activities): subsets = {0:-1} for (activity, cost) in activities.iteritems(): for prev_sum in subsets.keys(): new_sum = prev_sum + cost if 0 == new_sum: new_subset = [activity] while prev_sum: activity = subsets[prev_sum] new_subset.append(activity) prev_sum -= activities[activity] return sorted(new_subset) if new_sum in subsets: continue subsets[new_sum] = activity return [] 

También aplicar la tercera optimización da como resultado algo así como:

 def subset_summing_to_zero3 (activities): A=activities.items() mid=len(A)//2 def make_subsets(A): subsets = {0:-1} for (activity, cost) in A: for prev_sum in subsets.keys(): new_sum = prev_sum + cost if new_sum and new_sum in subsets: continue subsets[new_sum] = activity return subsets subsets = make_subsets(A[:mid]) subsets2 = make_subsets(A[mid:]) def follow_trail(new_subset,subsets,s): while s: activity = subsets[s] new_subset.append(activity) s -= activities[activity] new_subset=[] for s in subsets: if -s in subsets2: follow_trail(new_subset,subsets,s) follow_trail(new_subset,subsets2,-s) if len(new_subset): break return sorted(new_subset) 

Definir obligado a ser el mayor valor absoluto de los elementos. El beneficio algorítmico de la reunión en el enfoque medio depende mucho del límite.

Para un límite bajo (por ejemplo, límite = 1000 yn = 300) la reunión en el medio solo obtiene un factor de aproximadamente 2 mejoras, el otro es el primer método mejorado. Esto se debe a que el diccionario llamado subconjuntos está densamente poblado.

Sin embargo, para un límite alto (por ejemplo, límite = 100.000 y n = 30) la reunión en el medio toma 0.03 segundos en comparación con 2.5 segundos para el primer método mejorado (y 18 segundos para el código original)

Para límites altos, la reunión en el medio tomará aproximadamente la raíz cuadrada de la cantidad de operaciones del método normal.

Puede parecer sorprendente que encontrarse en el medio solo sea dos veces más rápido para los límites bajos. La razón es que el número de operaciones en cada iteración depende del número de teclas en el diccionario. Después de agregar k actividades, podríamos esperar que hubiera 2 ** k claves, pero si el límite es pequeño, muchas de estas teclas colisionarán, por lo que solo tendremos las teclas O (bound.k).

Pensé que compartiría mi solución Scala para el algoritmo pseudo-polytime descrito en wikipedia. Es una versión ligeramente modificada: se da cuenta de cuántos subconjuntos únicos hay. Esto está muy relacionado con un problema de HackerRank descrito en https://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers . El estilo de encoding podría no ser excelente, todavía estoy aprendiendo sobre Scala 🙂 Quizás esto todavía sea útil para alguien.

 object Solution extends App { var input = "1000\n2" System.setIn(new ByteArrayInputStream(input.getBytes())) println(calculateNumberOfWays(readInt, readInt)) def calculateNumberOfWays(X: Int, N: Int) = { val maxValue = Math.pow(X, 1.0/N).toInt val listOfValues = (1 until maxValue + 1).toList val listOfPowers = listOfValues.map(value => Math.pow(value, N).toInt) val lists = (0 until maxValue).toList.foldLeft(List(List(0)): List[List[Int]]) ((newList, i) => newList :+ (newList.last union (newList.last.map(y => y + listOfPowers.apply(i)).filter(z => z <= X))) ) lists.last.count(_ == X) } }