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 multiset de enteros y una suma objetivo , y la cuestión es decidir si algún subconjunto de los enteros suma con precisión . [1] Se sabe que el problema es NP-completo . Además, algunas variantes restringidas también son NP-completas, por ejemplo: [1]
- 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 sumas a cero.
- La variante en la que todas las entradas son positivas y la suma objetivo 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 .
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: n: el número de enteros de entrada y L: la precisión del problema, expresada como el número de valores posicionales binarios que se necesitan para plantear el problema.
- 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.
- 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 . [2] [3]
- 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 - 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 . [4]
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, puesto que hay subconjuntos y, para verificar cada subconjunto, necesitamos sumar como máximo n elementos.
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: [4]
- 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 [5] 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 decada. Para cada uno de estos dos conjuntos, almacena una lista de las sumas de todosposibles 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 para elementos, la lista se puede expandir a dos listas ordenadas con la introducción de un () th 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.
Schroeppel y Shamir
Schroeppel y Shamir [6] 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 el espacio anteriores complejidades ya que esto se puede hacer en y espacio dadas 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. [4]
Howgrave-Graham y Joux
Howgrave-Graham y Joux [7] 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 .
Las técnicas de Howgrave-Graham y Joux se ampliaron posteriormente [8] llevando la complejidad del tiempo a.
Solución de programación dinámica de tiempo pseudopolinomial
SSP se puede resolver en tiempo pseudopolinomial usando programación dinámica . Tenga en cuenta que esto implica que SSP solo es débilmente NP-Complete. Supongamos que tenemos la siguiente secuencia de elementos en una instancia:
ordenados en orden creciente y deseamos determinar si hay un subconjunto no vacío que sume a cero. Definir la función de valor booleano ser el valor o ) de
- "hay un subconjunto no vacío de que suma a . "
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.
Dejar ser la suma de los valores negativos y la suma de los valores positivos. Claramente,, Si o . Por tanto, no es necesario almacenar ni calcular estos valores.
Crea una matriz para contener los valores por y .
La matriz ahora se puede completar usando una recursividad simple. Inicialmente, para, colocar
dónde es una función booleana que devuelve verdadero si es igual a , falso en caso contrario.
Entonces para , colocar
- oo.
Para cada asignación, los valores de en el lado derecho ya se conocen, ya sea porque fueron almacenados en la tabla para el valor anterior de o porque Si o . Por lo tanto, el número total de operaciones aritméticas es. Por ejemplo, si todos los valores son para algunos , entonces el tiempo requerido es .
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 dónde es la suma que queremos encontrar en el conjunto de números. Esta solución no cuenta como tiempo polinomial en la teoría de la complejidad porqueno 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 de y , que son exponenciales en su número de bits.
Para el caso de que cada es positivo y está limitado por una constante fija , 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). [9] [10] En 2015, Koiliaris y Xu encontraron un determinista algoritmo para el problema de la suma de subconjuntos donde es la suma que necesitamos encontrar. [11] En 2017, Bringmann encontró unalgoritmo de tiempo. [12]
En 2014, Curtis y Sanches encontraron una recursividad simple altamente escalable en máquinas SIMD que tenían tiempo y espacio, donde es el número de elementos de procesamiento, y es el número entero más bajo. [13] 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 casos difíciles del SSP. [14]
Algoritmos de aproximación de tiempo polinomial
[ cita requerida ]
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 proporción aproximada de 1/2: [15]
- 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 relación de aproximación de . Su tiempo de ejecución es polinomio en y . Recuerde que n es el número de entradas y T es el límite superior de la suma del subconjunto.
inicializar una lista L para que contenga un elemento 0.para cada i de 1 a n hacer vamos U i ser una lista que contiene todos los elementos de Y en L , y todas las cantidades x i + y para todos y en L . ordenar U i en orden ascendente hacer que L esté vacío sea y el elemento más pequeño de U i agregue y a L para cada elemento z de U i en orden creciente . // Recorta la lista eliminando números cercanos entre sí // y tirar elementos mayores que la suma de destino T . si y + ε T / n < z ≤ T entonces y = z suma z a Ldevuelve el elemento más grande en L.
Tenga en cuenta que sin el paso de recorte (el bucle interno "para cada"), la lista L contendría las sumas de todossubconjuntos de entradas. El paso de recorte hace dos cosas:
- Asegura que todas las sumas restantes en L estén por debajo de T , por lo que son soluciones factibles al problema de la suma de subconjuntos.
- Asegura que la lista L es "escasa", es decir, la diferencia entre cada dos sumas parciales consecutivas es al menos .
Estas propiedades juntas garantizan que la lista contiene no más de elementos; por lo tanto, el tiempo de ejecución es polinomio en.
Cuando finaliza el algoritmo, si la suma óptima está en , luego se devuelve y ya está. De lo contrario, debe haberse eliminado en un paso de recorte anterior. Cada paso de recorte introduce un error aditivo de como máximo, entonces pasos juntos introducen un error de como máximo . Por lo tanto, la solución devuelta es al menos que es al menos .
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 los números se puede especificar con como máximo bits, luego resolviendo el problema aproximadamente con equivale a resolverlo exactamente. Luego, el algoritmo de tiempo polinomial para la suma aproximada del subconjunto se convierte en un algoritmo exacto con polinomio de tiempo de ejecución en y (es decir, exponencial en ).
Otro FPTAS para la suma de subconjuntos está disponible en. [dieciséis]
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. [17]
- Problema de suma de 4 subconjuntos. [18]
Referencias
- ↑ a b Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). pag. 491 . ISBN 0-321-37291-3.
- ^ Goodrich, Michael. "Más problemas NP completos y NP difíciles" (PDF) .
- ^ Informal-CS (2018). "Reducción: 3-CNF SAT a Subconjunto Suma" . Youtube .
- ^ a b c Richard E. Korf, Ethan L. Schreiber y Michael D. Moffitt (2014). "Partición numérica secuencial óptima de varias direcciones" (PDF) .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Horowitz, Ellis; Sahni, Sartaj (1974), "Computación de particiones con aplicaciones al problema de la mochila" (PDF) , Revista de la Asociación de Maquinaria de Computación , 21 (2): 277-292, doi : 10.1145 / 321812.321823 , hdl : 1813/5989 , Señor 0354006 , S2CID 16866858
- ^ Schroeppel, Richard; Shamir, Adi (1 de agosto de 1981). "A $ T = O (2 ^ {n / 2}) $, $ S = O (2 ^ {n / 4}) $ Algoritmo para ciertos problemas NP-Complete" . Revista SIAM de Computación . 10 (3): 456–464. doi : 10.1137 / 0210033 . ISSN 0097-5397 .
- ^ Howgrave-Graham, Nick; Joux, Antoine (2010). Gilbert, Henri (ed.). "Nuevos algoritmos genéricos para mochilas duras" . Avances en Criptología - EUROCRYPT 2010 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 6110 : 235–256. doi : 10.1007 / 978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.
- ^ Becker, Anja; Joux, Antoine (2010). Gilbert, Henri (ed.). "Nuevos algoritmos genéricos para mochilas duras" . Avances en Criptología - EUROCRYPT 2011 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 6632 : 364–385. doi : 10.1007 / 978-3-642-20465-4_21 . ISBN 978-3-642-20465-4.
- ^ http://hjemmesider.diku.dk/~pisinger/codes.html
- ^ Pisinger D (1999). "Algoritmos de tiempo lineal para problemas de mochila con pesos acotados". Journal of Algorithms , volumen 33, número 1, octubre de 1999, págs. 1-14
- ^ Koiliaris, Konstantinos; Xu, Chao (8 de julio de 2015). "Un algoritmo de tiempo pseudopolinomial más rápido para la suma del subconjunto". arXiv : 1507.02318 [ cs.DS ].
- ^ Bringmann K. Un algoritmo de tiempo pseudopolinomial casi lineal para la suma del subconjunto [C] // Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos. Sociedad de Matemáticas Industriales y Aplicadas, 2017: 1073-1084
- ^ Curtis, VV; Sanches, CAA (enero de 2016). "Una solución eficiente al problema de la suma de subconjuntos en la GPU: una solución eficiente al problema de la suma de subconjuntos en la GPU". Concurrencia y Computación: Práctica y Experiencia . 28 (1): 95-113. doi : 10.1002 / cpe.3636 . S2CID 20927927 .
- ^ Curtis, VV; Sanches, CAA (julio de 2017). "Un algoritmo de espacio bajo para el problema de la suma de subconjuntos en GPU". Investigación de Computación y Operaciones . 83 : 120-124. doi : 10.1016 / j.cor.2017.02.006 .
- ^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (1 de febrero de 2000). "El problema de la suma de subconjuntos múltiples" . Revista SIAM de Optimización . 11 (2): 308–319. doi : 10.1137 / S1052623498348481 . ISSN 1052-6234 .
- ^ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004), Problemas de mochila , Springer, p. 97, ISBN 9783540402862
- ^ Lagarias, JC; Odlyzko, AM (1 de enero de 1985). "Resolver problemas de suma de subconjuntos de baja densidad" . Revista de la ACM . 32 (1): 229–246. doi : 10.1145 / 2455.2461 . ISSN 0004-5411 .
- ^ Martello, Silvano; Toth, Paolo (1990). "Problema de suma de 4 subconjuntos" . Problemas de mochila: algoritmos e interpretaciones informáticas . Wiley-Interscience. págs. 105-136 . ISBN 0-471-92420-2. Señor 1086874 .
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.