Problema de suma de subconjuntos - Subset sum problem

El problema de la suma de subconjuntos (SSP) es un problema de decisión en informática . En su formulación más general, hay un conjunto múltiple de números enteros y una suma objetivo , y la cuestión es decidir si algún subconjunto de los números enteros suma con precisión . Se sabe que el problema es NP-completo . Además, algunas variantes restringidas también son NP-completas, por ejemplo: ${\ Displaystyle S}$${\ Displaystyle T}$${\ Displaystyle T}$

• La variante en la que todas las entradas son positivas.
• La variante en la que las entradas pueden ser positivas o negativas, y . Por ejemplo, dado el conjunto , la respuesta es sí porque el subconjunto suma cero.${\ Displaystyle T = 0}$${\ Displaystyle \ {- 7, -3, -2,9000,5,8 \}}$${\ Displaystyle \ {- 3, -2,5 \}}$
• La variante en la que todas las entradas son positivos, y la suma de destino es exactamente la mitad de la suma de todas las entradas, es decir, . Este caso especial de SSP se conoce como problema de partición .${\ Displaystyle T = {\ frac {1} {2}} (a_ {1} + \ dots + a_ {n})}$

SSP también puede ser considerado como un problema de optimización : encontrar un subconjunto cuya suma asciende como máximo a T , y sujeto a eso, lo más cerca posible a T . Es NP-hard , pero hay varios algoritmos que pueden resolverlo razonablemente rápido en la práctica.

SSP es un caso especial del problema de la mochila y del problema de la suma de subconjuntos múltiples .

Dureza computacional

La complejidad en tiempo de ejecución de SSP depende de dos parámetros:

norte

el número de enteros de entrada

• Si n (el número de enteros) es un número fijo pequeño, entonces es práctica una búsqueda exhaustiva de la solución.

L

la precisión del problema, expresada como el número de valores posicionales binarios que se necesitan para plantear el problema.

• Si L (el número de dígitos binarios) es un número fijo pequeño, entonces existen algoritmos de programación dinámica que pueden resolverlo exactamente.

Cuando tanto n como L son grandes, SSP es NP-hard. La complejidad de los algoritmos más conocidos es exponencial en el menor de los dos parámetros n y L . Se sabe que las siguientes variantes son NP-hard:

• Todos los enteros de entrada son positivos (y la suma objetivo T es parte de la entrada). Esto puede demostrarse mediante una reducción directa de 3SAT .
• Los números enteros de entrada pueden ser tanto positivos como negativos, y la suma objetivo T = 0. Esto se puede demostrar reduciendo la variante con números enteros positivos. Denote esa variante por SubsetSumPositive y la variante actual por SubsetSumZero. Dada una instancia ( S , T ) de SubsetSumPositive, construir una instancia de SubsetSumZero mediante la adición de un único elemento con el valor - T . Dada una solución a la instancia de SubsetSumPositive, la adición de - T produce una solución a la instancia de SubsetSumZero. Por el contrario, dada una solución a la instancia de SubsetSumZero, debe contener la - T (ya que todos los enteros en S son positivos), por lo que para obtener una suma de cero, también debe contener un subconjunto de S con una suma de + T , que es una solución de la instancia SubsetSumPositive.
• Los números enteros de entrada son positivos y T = suma ( S ) / 2. Esto también se puede probar reduciendo la variante general; ver problema de partición .

Algoritmos de tiempo exponencial

Hay varias formas de resolver SSP en tiempo exponencial en n .

Exclusión inclusión

El algoritmo más ingenuo sería recorrer todos los subconjuntos de n números y, para cada uno de ellos, verificar si el subconjunto suma el número correcto. El tiempo de ejecución es de orden , ya que hay subconjuntos y, para verificar cada subconjunto, necesitamos sumar como máximo n elementos. ${\ Displaystyle O (2 ^ {n} \ cdot n)}$${\ Displaystyle 2 ^ {n}}$

El algoritmo se puede implementar mediante la búsqueda en profundidad de un árbol binario: cada nivel del árbol corresponde a un número de entrada; la rama izquierda corresponde a excluir el número del conjunto, y la rama derecha corresponde a incluir el número (de ahí el nombre Inclusión-Exclusión). La memoria requerida es . El tiempo de ejecución se puede mejorar mediante varias heurísticas: ${\ Displaystyle O (n)}$

• Procese los números de entrada en orden descendente.
• Si los enteros incluidos en un nodo dado exceden la suma del mejor subconjunto encontrado hasta ahora, el nodo se poda.
• Si los enteros incluidos en un nodo dado, más todos los enteros restantes, son menores que la suma del mejor subconjunto encontrado hasta ahora, el nodo se poda.

Horowitz y Sahni

Horowitz y Sahni publicaron un algoritmo de tiempo exponencial más rápido, que se ejecuta en el tiempo , pero requiere mucho más espacio . El algoritmo divide arbitrariamente los n elementos en dos conjuntos de cada uno. Para cada uno de estos dos conjuntos, almacena una lista de las sumas de todos los posibles subconjuntos de sus elementos. A continuación, se ordena cada una de estas dos listas. Usando incluso el algoritmo de clasificación de comparación más rápido, Mergesort para este paso llevaría tiempo . Sin embargo, dada una lista ordenada de sumas de elementos, la lista se puede expandir a dos listas ordenadas con la introducción de un ( ) ésimo elemento, y estas dos listas ordenadas se pueden fusionar en el tiempo . Por lo tanto, cada lista se puede generar en forma ordenada en el tiempo . Dadas las dos listas ordenadas, el algoritmo puede verificar si un elemento de la primera matriz y un elemento de la segunda matriz suman T en el tiempo . Para hacer eso, el algoritmo pasa a través de la primera matriz en orden decreciente (comenzando en el elemento más grande) y la segunda matriz en orden creciente (comenzando en el elemento más pequeño). Siempre que la suma del elemento actual en la primera matriz y el elemento actual en la segunda matriz sea mayor que T , el algoritmo se mueve al siguiente elemento en la primera matriz. Si es menor que T , el algoritmo pasa al siguiente elemento de la segunda matriz. Si se encuentran dos elementos que suman T , se detiene. ${\ Displaystyle O (2 ^ {n / 2} \ cdot (n / 2))}$${\ Displaystyle O (2 ^ {n / 2})}$${\ Displaystyle n / 2}$${\ Displaystyle 2 ^ {n / 2}}$${\ Displaystyle O (2 ^ {n / 2} n)}$${\ Displaystyle k}$${\ Displaystyle k + 1}$${\ Displaystyle O (2 ^ {k})}$${\ Displaystyle O (2 ^ {n / 2})}$${\ Displaystyle O (2 ^ {n / 2})}$

Schroeppel y Shamir

Schroeppel y Shamir presentaron un algoritmo basado en Horowitz y Sanhi, que requiere un tiempo de ejecución similar , mucho menos espacio . En lugar de generar y almacenar todos los subconjuntos de n / 2 elementos por adelantado, dividen los elementos en 4 conjuntos de n / 4 elementos cada uno, y generan subconjuntos de n / 2 pares de elementos dinámicamente usando un montón mínimo que produce el tiempo y espacio anteriores complejidades ya que esto se puede hacer en un espacio dado 4 listas de longitud k. ${\ Displaystyle O (2 ^ {n / 2} \ cdot (n / 4))}$${\ Displaystyle O (2 ^ {n / 4})}$${\ Displaystyle O (k ^ {2} \ log (k))}$${\ Displaystyle O (k)}$

Debido a los requisitos de espacio, el algoritmo HS es práctico para hasta 50 enteros y el algoritmo SS es práctico para hasta 100 enteros.

Howgrave-Graham y Joux

Howgrave-Graham y Joux presentaron un algoritmo probabilístico que se ejecuta más rápido que todos los anteriores, en el tiempo usando el espacio . Es sólo resuelve el problema de decisión, no puede probar que no hay solución para una suma determinada, y no devuelve la suma de subconjuntos más cerca de T . ${\ displaystyle O (2 ^ {. 337n})}$${\ Displaystyle O (2 ^ {. 256n})}$

Las técnicas de Howgrave-Graham y Joux se ampliaron posteriormente aportando la complejidad del tiempo a . ${\ Displaystyle O (2 ^ {. 291n})}$

Solución de programación dinámica de tiempo pseudopolinomial

SSP se puede resolver en tiempo pseudopolinomial usando programación dinámica . También se observa que esto implica en sí mismo que Subconjunto Sum codificado en unario está en P ya que entonces, el tamaño de la codificación es lineal en el tamaño del número objetivo. Por lo tanto, Subset Sum es solo débilmente NP-Complete. Supongamos que tenemos la siguiente secuencia de elementos en una instancia:

${\ Displaystyle x_ {1}, \ ldots, x_ {N}}$

ordenados en orden creciente y deseamos determinar si hay un subconjunto no vacío que sume a cero. Defina la función de valor booleano como el valor ( verdadero o falso ) de ${\ Displaystyle Q (i, s)}$

"hay un subconjunto no vacío que suma s ".${\ Displaystyle x_ {1}, \ ldots, x_ {i}}$

Por tanto, la solución al problema "Dado un conjunto de números enteros, ¿existe un subconjunto no vacío cuya suma sea cero?" es el valor de . ${\ Displaystyle Q (N, 0)}$

Sea A la suma de los valores negativos y B la suma de los valores positivos. Claramente, . Por tanto, estos valores no necesitan almacenarse ni calcularse. ${\ Displaystyle Q (i, s) = {\ textit {false}} {\ text {, if}} s <A {\ text {o}} s> B}$

Cree una matriz para contener los valores . ${\ Displaystyle Q (i, s) {\ text {para}} 1 \ leq i \ leq N {\ text {y}} A \ leq s \ leq B}$

La matriz ahora se puede completar usando una recursividad simple. Inicialmente, para , establecer ${\ Displaystyle A \ leq s \ leq B}$

${\ Displaystyle Q (1, s): = (x_ {1} == s)}$

donde es una función booleana que devuelve verdadero si es igual as , falso en caso contrario. ${\ displaystyle ==}$${\ Displaystyle x_ {1}}$

Entonces, para , establecer ${\ Displaystyle i = 2, \ ldots, N}$

${\ Displaystyle Q (i, s): = Q (i-1, s) {\ text {o}} ((x_ {i} == s) {\ text {y}} Q (i-1, s -x_ {i})), {\ text {para}} A \ leq s \ leq B}$.

Para cada asignación, los valores de Q en el lado derecho ya se conocen, ya sea porque se almacenaron en la tabla para el valor anterior de i o porque . Por tanto, el número total de operaciones aritméticas es . Por ejemplo, si todos los valores son para algunos k , entonces el tiempo requerido es . ${\ Displaystyle Q (i-1, s-x_ {i}) = {\ textit {falso}} \ {\ text {if}} s-x_ {i} <A {\ text {o}} s-x_ {i}> B}$${\ Displaystyle O (N (BA))}$${\ Displaystyle O (N ^ {k})}$${\ Displaystyle O (N ^ {k + 2})}$

Este algoritmo se modifica fácilmente para devolver el subconjunto con la suma 0 si hay uno.

La solución de programación dinámica tiene un tiempo de ejecución de donde s es la suma que queremos encontrar en un conjunto de N números. Esta solución no cuenta como tiempo polinomial en la teoría de la complejidad porque no es polinomial en el tamaño del problema, que es el número de bits utilizados para representarlo. Este algoritmo es polinomio en los valores de A y B , que son exponenciales en su número de bits. ${\ Displaystyle O (sN)}$${\ displaystyle BA}$

Para el caso de que cada uno sea ​​positivo y esté limitado por una constante fija C , Pisinger encontró un algoritmo de tiempo lineal que tiene complejidad de tiempo (tenga en cuenta que esto es para la versión del problema donde la suma objetivo no es necesariamente cero, de lo contrario el problema sería trivial ). En 2015, Koiliaris y Xu encontraron un algoritmo determinista para el problema de la suma de subconjuntos donde s es la suma que necesitamos encontrar. En 2017, Bringmann encontró un algoritmo de tiempo aleatorio . ${\ Displaystyle x_ {i}}$${\ Displaystyle O (NC)}$${\ Displaystyle {\ tilde {O}} (s {\ sqrt {N}})}$${\ Displaystyle {\ tilde {O}} (s + N)}$

En 2014, Curtis y Sanches encontraron una recursividad simple altamente escalable en máquinas SIMD que tienen tiempo y espacio, donde p es el número de elementos de procesamiento y es el número entero más bajo. Esta es la mejor complejidad paralela teórica conocida hasta ahora. ${\ Displaystyle O (N (m-x _ {\ min}) / p)}$${\ Displaystyle O (N + m-x _ {\ min})}$${\ Displaystyle m = \ min (s, \ sum x_ {i} -s)}$${\ Displaystyle x _ {\ min}}$

Curtis y Sanches analizan una comparación de los resultados prácticos y la solución de casos difíciles del SSP.

Algoritmos de aproximación de tiempo polinomial

Suponga que todas las entradas son positivas. Un algoritmo de aproximación a SSP tiene como objetivo encontrar un subconjunto de S con una suma de como máximo T y al menos r veces la suma óptima, donde r es un número en (0,1) llamado relación de aproximación .

Aproximación 1/2 simple

El siguiente algoritmo muy simple tiene una relación de aproximación de 1/2:

• Ordene las entradas por valor descendente;
• Coloque la siguiente entrada más grande en el subconjunto, siempre que encaje allí.

Cuando este algoritmo termina, todas las entradas están en el subconjunto (que obviamente es óptimo) o hay una entrada que no encaja. La primera entrada de este tipo es más pequeña que todas las entradas anteriores que están en el subconjunto, por lo que debe ser más pequeña que T / 2. Por lo tanto, la suma de las entradas en el subconjunto es más que T / 2, que obviamente es más que OPT / 2.

Esquema de aproximación de tiempo completamente polinomial

El siguiente algoritmo alcanza, para cada , una razón de aproximación de . Su tiempo de ejecución es polinomio en n y . Recuerde que n es el número de entradas y T es el límite superior de la suma del subconjunto. ${\ Displaystyle \ epsilon> 0}$${\ Displaystyle (1- \ epsilon)}$${\ Displaystyle 1 / \ epsilon}$

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

Tenga en cuenta que sin el paso de recorte (el bucle interno "para cada"), la lista L contendría las sumas de todos los subconjuntos de entradas. El paso de recorte hace dos cosas: ${\ Displaystyle 2 ^ {n}}$

• Asegura que todas las sumas restantes en L estén por debajo de T , por lo que son soluciones factibles para el problema de la suma de subconjuntos.
• Asegura que la lista L sea "escasa", es decir, que la diferencia entre cada dos sumas parciales consecutivas sea al menos .${\ Displaystyle \ epsilon T / n}$

Estas propiedades juntas garantizan que la lista L no contenga más que elementos; por lo tanto, el tiempo de ejecución es polinomial en . ${\ Displaystyle n / \ epsilon}$${\ Displaystyle n / \ epsilon}$

Cuando finaliza el algoritmo, si la suma óptima está en L , se devuelve y terminamos. De lo contrario, debe haberse eliminado en un paso de recorte anterior. Cada paso de recorte introduce un error aditivo de como máximo , por lo que n pasos juntos introducen un error de como máximo . Por lo tanto, la solución devuelta es al menos cuál es al menos . ${\ Displaystyle \ epsilon T / n}$${\ Displaystyle \ epsilon T}$${\ Displaystyle {\ text {OPT}} - \ epsilon T}$${\ Displaystyle (1- \ epsilon) {\ text {OPT}}}$

El algoritmo anterior proporciona la solución para el problema de la suma del subconjunto original en el caso de que los números sean pequeños (nuevamente, para números no negativos). Si cualquier suma de números puede especificarse con un máximo de P bits, entonces resolver el problema aproximadamente con es equivalente a resolverlo exactamente. Entonces, el algoritmo de tiempo polinómico para la suma de subconjuntos aproximada se convierte en un algoritmo exacto con el funcionamiento de polinomio tiempo en n y (es decir, exponencial de P ). ${\ Displaystyle \ epsilon = 2 ^ {- P}}$${\ Displaystyle 2 ^ {P}}$

Kellerer, Mansini, Pferschy y Speranza y Kellerer, Pferschy y Pisinger presentan otros FPTAS-s para la suma del subconjunto.

Ver también

• Problema de la mochila : una generalización de SSP en la que cada elemento de entrada tiene un valor y un peso. El objetivo es maximizar el valor de manera que el peso total esté acotado.
• Problema de suma de subconjuntos múltiples : una generalización de SSP en la que se deben elegir varios subconjuntos.
• 3SUM
• Criptosistema de mochila Merkle-Hellman
• Un algoritmo para resolver SSP de baja densidad con alta probabilidad.
• Problema de suma de 4 subconjuntos.

Referencias

Otras lecturas

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "35,5: El problema de la suma de subconjuntos". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03293-7.
• Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0-7167-1045-5. A3.2: SP13, página 223.