algorithm - simbolo - qué es un problema np hard
Solución rápida a la suma de subconjuntos (6)
¡Respeto la prontitud con la que intentas resolver este problema! Desafortunadamente, estás tratando de resolver un problema que es NP-completo , lo que significa que cualquier mejora adicional que rompa la barrera del tiempo polinomial demostrará que P = NP .
La implementación que obtuvo de Hacker News parece ser consistente con la solución de programació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: si bien 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 de error tolerable. En el 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 suma objetivo.
Para más detalles, vea el artículo de Wikipedia .
Considere esta manera de resolver el problema de la suma de subconjuntos:
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 lleve a acelerar. Encontré:
https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2
que menciona un algoritmo de tiempo lineal. Pero no tengo el papel, tal vez ustedes, queridos, ¿saben cómo funciona? ¿Una implementación tal vez? ¿Un enfoque completamente diferente tal vez?
Editar 2
Ahora hay un seguimiento:
Solución rápida para el algoritmo de suma de subconjuntos por Pisinger
Aquí hay tres formas de hacer que el código sea más eficiente:
El código almacena una lista de actividades para cada suma parcial. Es más eficiente en términos de memoria y tiempo almacenar solo la actividad más reciente necesaria para hacer la suma, y resolver el resto al retroceder una vez que se encuentre una solución.
Para cada actividad, el diccionario se vuelve a llenar con los contenidos antiguos (subconjuntos [prev_sum] = subconjunto). Es más rápido simplemente crecer un solo diccionario
Dividir los valores en dos y aplicar un encuentro en el enfoque medio.
La aplicación de las dos primeras optimizaciones da como resultado el siguiente código, que es 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 aplicando los resultados de la tercera optimización en algo 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, enlazado = 1000 y n = 300), el encuentro en el medio solo obtiene un factor de aproximadamente 2 mejoras, 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 yn = 30), el encuentro 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, el encuentro en el medio tomará aproximadamente la raíz cuadrada del número de operaciones del método normal.
Puede parecer sorprendente que el encuentro en el medio sea solo el doble de rápido que para los límites bajos. La razón es que el número de operaciones en cada iteración depende del número de claves en el diccionario. Después de agregar k actividades, podemos esperar que haya 2 ** k claves, pero si el límite es pequeño, muchas de estas claves colisionarán, por lo que solo tendremos claves O (bound.k) en su lugar.
Me disculpo por "discutir" el problema, pero un problema de "Suma de subconjunto" donde los valores de x están limitados no es la versión NP del problema. Las soluciones de programación dinámica son conocidas por problemas de valor acotado x. Esto se hace representando los valores de x como la suma de longitudes de unidades. Las soluciones de programación dinámica tienen una serie de iteraciones fundamentales que son lineales con esa longitud total de las x. Sin embargo, la suma de los subconjuntos está en NP cuando la precisión de los números es igual a N. Es decir, el número o los valores de posición de base 2 necesarios para indicar las x son = N. Para N = 40, las x tienen que estar en los miles de millones. En el problema de NP, la longitud de la unidad de las x aumenta exponencialmente con N. Es por eso que las soluciones de programación dinámica no son una solución de tiempo polinomial para el problema de la suma de subconjuntos de NP. Siendo ese el caso, todavía hay ejemplos prácticos del problema de la suma de subconjuntos donde los x están limitados y la solución de programación dinámica es válida.
No sé mucho de python, pero hay un enfoque llamado reunirse en el medio. 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 el número de elementos de actividades que puede manejar en un tiempo razonable.
Pensé que compartiría mi solución Scala para el algoritmo de pseudo-polytime descrito en wikipedia. Es una versión ligeramente modificada: calcula 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 codificación puede no ser excelente, todavía estoy aprendiendo Scala :) Tal vez 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)
}
}
Si bien mi respuesta anterior describe el algoritmo de aproximación de polytime a este problema, se realizó una solicitud específicamente para una implementación de la solución de programación dinámica 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 inductor de dolor de cabeza. Esto necesita revisión, ya que, mientras implementa balsub , no puedo definir el comparador correcto para determinar si existe la solución óptima para este subproblema de SSP.