Problema de suma de subconjuntos

El subset sum problem (SSP) es un problema de decisión en la informática. En su formulación más general, hay un multiset ${displaystyle S.$ of integers and a target-sum ${displaystyle T}$, y la cuestión es decidir si cualquier subconjunto de los enteros suma precisamente ${displaystyle T}$. Se sabe que el problema es NP-hard. Además, algunas variantes restringidas de la misma son completas por NP, por ejemplo:

• La variante en la que todos los insumos son positivos.
• La variante en la que los insumos pueden ser positivos o negativos, y ${displaystyle T=0}$. Por ejemplo, dado el conjunto ${displaystyle {-7,-3,-2,9000,5}}$, la respuesta es Sí. porque el subconjunto ${displaystyle {-3,-2,5}}$ sumas a cero.
• La variante en la que todos los insumos son positivos, y la suma de destino es exactamente la mitad de la suma de todos los insumos, es decir, ${displaystyle T={frac {1}{2}(a_{1}+dots +a_{n}}$. Este caso especial de SSP es conocido como el problema de la partición.

SSP también se puede considerar como un problema de optimización: encuentre un subconjunto cuya suma sea como máximo T y, sujeto a eso, lo más cerca posible de T. Es NP-difícil, pero existen 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 múltiples subconjuntos.

Dureza computacional

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

• n - el número de enteros de entrada. Si n es un pequeño número fijo, entonces una búsqueda exhaustiva de la solución es práctica.
• L - la precisión del problema, declarado como el número de valores binarios del lugar que se necesita para indicar el problema. Si L es un pequeño número fijo, entonces hay algoritmos de programación dinámica que pueden resolverlo exactamente.

A medida que tanto n como L crecen, SSP es NP-duro. La complejidad de los algoritmos más conocidos es exponencial en el menor de los dos parámetros n y L. El problema es NP-difícil incluso cuando todos los enteros de entrada son positivos (y la suma objetivo T es parte de la entrada). Esto se puede demostrar mediante una reducción directa de 3SAT. También se puede demostrar por reducción a partir de coincidencia tridimensional (3DM):

• Se nos da una instancia de 3DM, donde los conjuntos de vértice son W, X, Y. Cada conjunto tiene n vertices. Hay m bordes, donde cada borde contiene exactamente un vértice de cada uno de W, X, Y. Denote L:= techo(log)₂()m+1)), así L es mayor que el número de bits requeridos para representar el número de bordes.
• Construimos una instancia de SSP con m enteros positivos. Los enteros son descritos por su representación binaria. Cada entero de entrada puede ser representado por 3nL bits, divididos en 3n zonas de L bits. Cada zona corresponde a un vértice.
• Para cada borde (w,x,y) en la instancia 3DM, hay un entero en la instancia SSP, en la que exactamente tres bits son "1": los bits menos significativos en las zonas de los vértices w, x, y. Por ejemplo, si n=10 y L=3, y W=(0,...,9), X=(10,...,19), Y=(20,...,29), entonces el borde (0, 10, 20) está representado por el número (2⁰+2³⁰+2⁶⁰).
• La suma de destino T en la instancia SSP se establece a un entero con "1" en el pedazo menos significativo de cada zona, es decir, (2⁰+2¹+...+2^3n-1).
• Si la instancia 3DM tiene una combinación perfecta, entonces resumir los enteros correspondientes en la instancia SSP produce exactamente T.
• Por el contrario, si la instancia SSP tiene un subconjunto con suma exactamente T, entonces, ya que las zonas son suficientemente grandes para que no haya "carries" de una zona a la siguiente, la suma debe corresponder a una combinación perfecta en la instancia 3DM.

También se sabe que las siguientes variantes son NP-duras:

• Los enteros de entrada pueden ser tanto positivos como negativos, y la suma de destino T = 0. Esto puede ser probado por reducción de la variante con enteros positivos. Denota esa variante por SubsetSumPositive y la variante actual por SubsetSumZero. Dado un caso (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value −T. Dada una solución al caso SubsetSumPositive, añadiendo el −T produce una solución a la instancia SubsetSumZero. Por el contrario, dada una solución a la instancia SubsetSumZero, debe contener el −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 enteros de entrada son positivos, y T = sumaS)/2. Esto también puede ser probado por reducción de la variante general; ver problema de partición.

Algoritmos de tiempo exponencial

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

Inclusión–exclusión

El algoritmo más ingenuo sería el ciclo a través de todos los subconjuntos de n números y, para cada uno de ellos, comprobar si el subconjunto suma al número correcto. El tiempo de funcionamiento es de orden ${displaystyle O(2^{n}cdot n)}$, ya que hay ${displaystyle 2^{n}$ subconjuntos y, para comprobar cada subconjunto, necesitamos resumir al máximo n elementos.

El algoritmo se puede aplicar mediante la búsqueda de profundidad-primera de un árbol binario: cada nivel en el á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 Inclusion-Exclusion). La memoria requerida es ${displaystyle O(n)}$. El tiempo de ejecución puede ser mejorado por varias heurísticas:

• Procesar 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 es podado.
• Si los enteros incluidos en un nodo dado, más todos los enteros restantes, son menos que la suma de los mejores subconjuntos encontrados hasta ahora, el nodo es podado.

Horowitz y Sahni

En 1974, Horowitz y Sahni publicaron un algoritmo de tiempo exponencial más rápido, que funciona en el tiempo ${displaystyle O(2^{n/2}cdot (n/2)}$, pero requiere mucho más espacio - ${displaystyle O(2^{n/2}}$. El algoritmo se divide arbitrariamente n elementos en dos conjuntos ${displaystyle n/2}$ cada uno. Para cada uno de estos dos conjuntos, almacena una lista de las sumas de todos ${displaystyle 2^{n/2}$ posibles subconjuntos de sus elementos. Cada una de estas dos listas está ordenada. Usando incluso el algoritmo de clasificación de comparación más rápido, Mergesort para este paso tomaría tiempo ${displaystyle O(2^{n/2}n)}$. Sin embargo, dada una lista ordenada de sumas para ${displaystyle k}$ elementos, la lista se puede ampliar a dos listas clasificadas con la introducción de a (${displaystyle k+1}$) el elemento, y estas dos listas clasificadas se pueden fusionar en el tiempo ${displaystyle O(2^{k}}$. Así, cada lista puede ser generada en forma ordenada en el tiempo ${displaystyle O(2^{n/2}}$. Dada las dos listas clasificadas, el algoritmo puede comprobar si un elemento de la primera matriz y un elemento de la segunda matriz suma hasta T en el tiempo ${displaystyle O(2^{n/2}}$. Para ello, el algoritmo pasa a través de la primera matriz en el orden decreciente (a partir del elemento más grande) y la segunda matriz en orden creciente (a partir del elemento más pequeño). Cada vez que la suma del elemento actual en la primera matriz y el elemento actual en la segunda matriz es más que T, el algoritmo se mueve al siguiente elemento en el primer array. Si es menos que T, el algoritmo se mueve al siguiente elemento en el segundo array. Si dos elementos que suma T se encuentran, se detiene. (El subproblema para dos elementos suma se conoce como dos sumas.)

Schroeppel y Shamir

En 1981, Schroeppel y Shamir presentaron un algoritmo basado en Horowitz y Sanhi, que requiere tiempo de ejecución similar - ${displaystyle O(2^{n/2}cdot (n/4)}$, mucho menos espacio - ${displaystyle O(2^{n/4}}$. En lugar de generar y almacenar todos los subconjuntos de n/2 elementos de antemano, que particionan los elementos en 4 conjuntos de n/4 elementos cada uno, y generar subconjuntos de n/2 elemento uniforme dinámicamente utilizando un montón de minutos, que produce las complejidades de tiempo y espacio anteriores ya que esto se puede hacer en ${displaystyle O(k^{2}log(k)}$ y espacio ${displaystyle O(k)}$ dado 4 listas de longitud 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 funciona más rápido que todos los anteriores - en el tiempo ${displaystyle O(2^{.337n}$ utilizando espacio ${displaystyle O(2^{.256n}$. Sólo resuelve el problema de la decisión, no puede probar que no haya solución para una determinada suma, y no devuelve la suma del subconjunto más próxima a T.

The techniques of Howgrave-Graham and Joux were subsequently extended bringing the time-complexity to ${displaystyle O(2^{.291n}$.

Soluciones de programación dinámica de tiempo pseudo-polinomiales

SSP se puede resolver en tiempo pseudopolinomial usando programación dinámica. Supongamos que tenemos la siguiente secuencia de elementos en una instancia:

${displaystyle x_{1},ldotsx_{N}$

Definimos un estado como un par (i, s) de números enteros. Este estado representa el hecho de que

"hay un subconjunto no vacío ${displaystyle x_{1},ldotsx_{i}$ que suma s."

Cada estado (i, s) tiene dos estados siguientes:

• ()i+1, s), implicando que ${displaystyle x_{i+1}}$ no está incluido en el subconjunto;
• ()i+1, s+${displaystyle x_{i+1}}$), implicando que ${displaystyle x_{i+1}}$ está incluido en el subconjunto.

A partir del estado inicial (0, 0), es posible utilizar cualquier algoritmo de búsqueda de gráfico (por ejemplo, BFS) para buscar el estado (N, T). Si se encuentra el estado, retrocediendo podemos encontrar un subconjunto con una suma de exactamente T.

El tiempo de ejecución de este algoritmo es muy lineal en el número de estados. El número de estados es en la mayoría N veces el número de diferentes sumas posibles. Vamos A ser la suma de los valores negativos y B la suma de los valores positivos; el número de diferentes sumas posibles es al máximo B-A, así que el tiempo de ejecución total está en ${displaystyle O(N(B-A)}$. Por ejemplo, si todos los valores de entrada son positivos y están vinculados por alguna constante C, entonces B es en la mayoría N C, por lo que el tiempo requerido es ${displaystyle O(N^{2}C)}$.

Esta solución no cuenta como tiempo polinomio en la teoría de la complejidad porque ${displaystyle B-A}$ no es polinomio en el tamaño del problema, que es el número de bits utilizados para representarlo. Este algoritmo es polinomio en los valores A y B, que son exponenciales en sus números de bits. Sin embargo, Subset Sum codificado en no está en P, ya que entonces el tamaño de la codificación es lineal en B-A. Por lo tanto, Subset Sum es sólo débil NP-Complete.

Para el caso de que cada uno ${displaystyle x_{i}}$ es positivo y vinculado por una constante fija C, Pisinger encontró un algoritmo de tiempo lineal con complejidad de tiempo ${displaystyle O(NC)}$ (nota que esto es para la versión del problema donde la suma de destino no es necesariamente cero, de lo contrario el problema sería trivial). En 2015, Koiliaris y Xu encontraron un determinista ${displaystyle {tilde {fn} {fn}} {fn}} {fn}} {fn}} {fn}}}} {fn}}} {fn}}}}} {fn}}}} {fn}}}} {f}}}}}}}}$ algoritmo para el problema de la suma de subconjunto donde T es la suma que necesitamos encontrar. En 2017, Bringmann encontró un aleatorizado ${displaystyle {tilde {0}(T+N)}$ algoritmo de tiempo.

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

Curtis y Sanches analizan una comparación de los resultados prácticos y la solución de instancias 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 proporción de aproximación.

Simple 1/2-aproximación

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

• Ordenar las entradas por valor descendente;
• Ponga la entrada más grande en el subconjunto, siempre y cuando se ajuste allí.

Cuando finaliza este algoritmo, todas las entradas están en el subconjunto (lo 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 y la suma de las entradas en el subconjunto es mayor que T/2; de lo contrario, la entrada también es menor que T/2 y encajaría en el conjunto Tal suma mayor que T/2 es obviamente mayor que OPT/2.

Esquema de aproximación de tiempo totalmente polinomial

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

inicializar una lista L para contener un elemento 0.

para cada uno i de 1 a 1 n doDeja Ui ser una lista que contenga todos los elementos Sí. dentro L, y todas las sumas xi + Sí. para todos Sí. dentro L.
especie Ui en orden ascendente
hacer L vacío
Deja Sí. ser el elemento más pequeño Uiañadir Sí. a L para cada uno elemento z de Ui en orden creciente do // Trim la lista eliminando números cercanos unos a otros // y tirar elementos más grandes que la suma de destino T. si Sí. + ε T/n. z ≤ T entonces Sí. = zañadir z a Lretorno el elemento más grande en L.

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

• Garantiza que todas las sumas queden L a continuación T, por lo que son soluciones factibles para el problema de subconsumo.
• Garantiza que la lista L es "sparse", es decir, la diferencia entre cada dos sumas parciales consecutivas es al menos ${displaystyle epsilon T/n}$.

Estas propiedades juntas garantizan que la lista L no contiene más que ${displaystyle n/epsilon }$ elementos; por lo tanto el tiempo de ejecución es polinomio en ${displaystyle n/epsilon }$.

Cuando el algoritmo termina, si la suma óptima está en L, entonces es devuelto y hemos terminado. De lo contrario, debe haber sido removido en un paso anterior. Cada paso de recorte introduce un error aditivo de la mayoría ${displaystyle epsilon T/n}$Así que n pasos juntos introducir un error de la mayoría ${displaystyle epsilon T}$. Por lo tanto, la solución devuelta es al menos ${displaystyle {text{OPT}-epsilon T}$ por lo menos ${displaystyle (1-epsilon){text{OPT}}$.

El algoritmo anterior proporciona un exacta solución a SSP en el caso de que los números de entrada son pequeños (y no negativos). Si alguna suma de los números se puede especificar con la mayoría P bits, luego resolver el problema aproximadamente con ${displaystyle epsilon =2^{-P}$ es equivalente a resolverlo exactamente. Luego, el algoritmo de tiempo polinomio para la suma de subconjunto aproximada se convierte en un algoritmo exacto con el tiempo de funcionamiento polinomio en n y ${displaystyle 2^{P}$ (es decir, exponencial en P).

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