Problema de partición

En teoría de números y ciencias de la computación , el problema de partición , o partición de números , ^[1] es la tarea de decidir si un multiconjunto dado S de números enteros positivos se puede dividir en dos subconjuntos S ₁ y S ₂ de manera que la suma de los números en S ₁ sea igual a la suma de los números en S ₂ . Aunque el problema de partición es NP-completo , existe una solución de programación dinámica en tiempo pseudopolinomial , y hay heurísticas que resuelven el problema en muchos casos, ya sea de manera óptima o aproximada. Por esta razón, se lo ha llamado "el problema difícil más fácil". ^[2]^[3]

Existe una versión optimizada del problema de partición, que consiste en particionar el multiconjunto S en dos subconjuntos S ₁ , S ₂ de manera que se minimice la diferencia entre la suma de elementos en S ₁ y la suma de elementos en S _2. La versión optimizada es NP-hard , pero se puede resolver de manera eficiente en la práctica. ^[4]

El problema de la partición es un caso especial de dos problemas relacionados:

En el problema de la suma de subconjuntos , el objetivo es encontrar un subconjunto de S cuya suma sea un cierto número objetivo T dado como entrada (el problema de la partición es el caso especial en el que T es la mitad de la suma de S ).
En la partición de números multidireccional , hay un parámetro entero k y el objetivo es decidir si S se puede dividir en k subconjuntos de suma igual (el problema de partición es el caso especial en el que k = 2).

Sin embargo, es bastante diferente al problema de partición triple : en ese problema, el número de subconjuntos no está fijado de antemano; debe ser | S |/3, donde cada subconjunto debe tener exactamente 3 elementos. La partición triple es mucho más difícil que la partición: no tiene un algoritmo de tiempo pseudopolinomial a menos que P = NP . ^[5]

Ejemplos

Dado S = {3,1,1,2,2,1}, una solución válida para el problema de partición son los dos conjuntos S ₁ = {1,1,1,2} y S ₂ = {2,3}. Ambos conjuntos suman 5 y dividen S . Nótese que esta solución no es única. S ₁ = {3,1,1} y S ₂ = {2,2,1} es otra solución.

No todos los multiconjuntos de números enteros positivos tienen una partición en dos subconjuntos con sumas iguales. Un ejemplo de un conjunto de este tipo es S = {2,5}.

Dificultad computacional

El problema de partición es NP difícil. Esto se puede demostrar mediante reducción a partir del problema de suma de subconjuntos . ^[6] Una instancia de SubsetSum consiste en un conjunto S de números enteros positivos y una suma objetivo T ; el objetivo es decidir si hay un subconjunto de S con suma exactamente T .

Dada tal instancia, construya una instancia de Partición en la que el conjunto de entrada contenga el conjunto original más dos elementos: z ₁ y z ₂ , con z ₁ = suma(S) y z ₂ = 2 T . La suma de este conjunto de entrada es suma( S ) + z ₁ + z ₂ = 2 suma( S ) + 2 T , por lo que la suma objetivo para Partición es suma( S ) + T .

Supongamos que existe una solución S ′ para la instancia SubsetSum. Entonces, suma( S ′) = T , por lo que suma(S′ ∪ z_1) = suma( S ) + T , por lo que S ′ ∪ z_1 es una solución para la instancia Partition.
Por el contrario, supongamos que existe una solución S ′′ para la instancia Partition. Entonces, S ′′ debe contener z ₁ o z ₂ , pero no ambos, ya que su suma es mayor que sum( S ) + T . Si S'' contiene z ₁ , entonces debe contener elementos de S con una suma de exactamente T , por lo que S'' menos z ₁ es una solución para la instancia SubsetSum. Si S'' contiene z ₂ , entonces debe contener elementos de S con una suma de exactamente sum( S ) − T , por lo que los otros objetos en S son una solución para la instancia SubsetSum.

Algoritmos de aproximación

Como se mencionó anteriormente, el problema de la partición es un caso especial de partición multidireccional y de suma de subconjuntos. Por lo tanto, se puede resolver mediante algoritmos desarrollados para cada uno de estos problemas. Los algoritmos desarrollados para la partición de números multidireccional incluyen:

Partición de números voraz : recorre los números y coloca cada número en el conjunto cuya suma actual sea la más pequeña. Si los números no están ordenados, entonces el tiempo de ejecución es O( n ) y la razón de aproximación es como máximo 3/2 ("razón de aproximación" significa la suma más grande en la salida del algoritmo, dividida por la suma más grande en una partición óptima). Ordenar los números aumenta el tiempo de ejecución a O( n log n ) y mejora la razón de aproximación a 7/6. Si los números se distribuyen uniformemente en [0,1], entonces la razón de aproximación es como máximo casi con seguridad yen expectativa. ${\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}$ ${\textstyle 1+O\izquierda({\frac {1}{n}}\derecha)}$
El método de diferenciación más grande (también llamado algoritmo Karmarkar-Karp ) ordena los números en orden descendente y reemplaza repetidamente los números por sus diferencias. La complejidad en tiempo de ejecución es O( n log n ). En el peor de los casos, su razón de aproximación es similar: como máximo 7/6 . Sin embargo, en el caso promedio, funciona mucho mejor que el algoritmo voraz: cuando los números se distribuyen uniformemente en [0,1], su razón de aproximación está como máximoen la expectativa. También funciona mejor en experimentos de simulación. ${\textstyle 1+1/n^{\Theta (\log n)}}$
El algoritmo multifit utiliza una búsqueda binaria combinada con un algoritmo de empaquetamiento de bins . En el peor de los casos, su relación de aproximación es 8/7 .
El problema de la suma de subconjuntos tiene un FPTAS que también se puede usar para el problema de partición, estableciendo la suma objetivo en suma( S )/2.

Algoritmos exactos

Existen algoritmos exactos que siempre encuentran la partición óptima. Dado que el problema es NP-hard, dichos algoritmos pueden requerir un tiempo exponencial en general, pero pueden ser prácticamente utilizables en ciertos casos. Los algoritmos desarrollados para la partición de números multidireccional incluyen:

La partición del número de tiempo pseudopolinomial toma memoria, donde $m$ es el número más grande en la entrada. ${\textstyle O(nm)}$
El algoritmo voraz completo (CGA) considera todas las particiones mediante la construcción de un árbol binario . Cada nivel del árbol corresponde a un número de entrada, donde la raíz corresponde al número más grande, el nivel inferior al siguiente número más grande, etc. Cada rama corresponde a un conjunto diferente en el que se puede colocar el número actual. Recorrer el árbol en orden de profundidad requiere solo espacio, pero puede llevar tiempo. El tiempo de ejecución se puede mejorar utilizando una heurística voraz: en cada nivel, se desarrolla primero la rama en la que se coloca el número actual en el conjunto con la suma más pequeña. Este algoritmo encuentra primero la solución encontrada por la partición voraz de números , pero luego procede a buscar mejores soluciones. Algunas variaciones de esta idea son esquemas de aproximación de tiempo completamente polinomial para el problema de la suma de subconjuntos y, por lo tanto, también para el problema de la partición. ^[7]^[8] ${\textstyle O(n)}$ ${\textstyle O(2^{n})}$
El algoritmo completo Karmarkar-Karp (CKK) considera todas las particiones mediante la construcción de un árbol binario. Cada nivel corresponde a un par de números. La rama izquierda corresponde a ponerlos en diferentes subconjuntos (es decir, reemplazarlos por su diferencia), y la rama derecha corresponde a ponerlos en el mismo subconjunto (es decir, reemplazarlos por su suma). Este algoritmo encuentra primero la solución encontrada por el método de diferenciación más grande , pero luego procede a encontrar mejores soluciones. Se ejecuta sustancialmente más rápido que CGA en instancias aleatorias. Su ventaja es mucho mayor cuando existe una partición igual, y puede ser de varios órdenes de magnitud. En la práctica, los problemas de tamaño arbitrario pueden resolverse mediante CKK si los números tienen como máximo 12 dígitos significativos . ^[9] CKK también puede ejecutarse como un algoritmo en cualquier momento : encuentra primero la solución KK y luego encuentra soluciones progresivamente mejores a medida que el tiempo lo permite (posiblemente requiriendo tiempo exponencial para alcanzar la optimalidad, para los peores casos). ^[1] Requiere espacio, pero en el peor de los casos puede llevar tiempo. $En)$ $O(2^{n})$

Los algoritmos desarrollados para la suma de subconjuntos incluyen:

Horowitz y Sanhi : corre en el tiempo , pero requiere espacio. $O(2^{n/2}\cdot (n/2))$ $O(2^{n/2})$
Schroeppel y Shamir – corre en el tiempo y requiere mucho menos espacio – . $O(2^{n/2}\cdot (n/4))$ ${\textstyle O(2^{n/4})}$
Howgrave-Graham y Joux : se ejecuta en el tiempo , pero es un algoritmo aleatorio que solo resuelve el problema de decisión (no el problema de optimización). ${\textstyle O(2^{n/3})}$

Instancias difíciles y transición de fase

Los conjuntos con una sola partición o sin partición tienden a ser más difíciles (o más costosos) de resolver en comparación con sus tamaños de entrada. Cuando los valores son pequeños en comparación con el tamaño del conjunto, es más probable que se obtengan particiones perfectas. Se sabe que el problema sufre una " transición de fase "; es probable para algunos conjuntos y poco probable para otros. Si m es el número de bits necesarios para expresar cualquier número en el conjunto y n es el tamaño del conjunto, entonces tiende a tener muchas soluciones y tiende a tener pocas o ninguna solución. A medida que n y m se hacen más grandes, la probabilidad de una partición perfecta llega a 1 o 0 respectivamente. Esto fue argumentado originalmente con base en evidencia empírica por Gent y Walsh ^[10] , luego utilizando métodos de física estadística por Mertens ^[11]^[12] y luego demostrado por Borgs , Chayes y Pittel ^{[13] .} ${\estilo de visualización m/n<1}$ $m/n>1$

Versión probabilística

Un problema relacionado, algo similar a la paradoja del cumpleaños , es el de determinar el tamaño del conjunto de entrada de modo que tengamos una probabilidad de la mitad de que exista una solución, bajo el supuesto de que cada elemento del conjunto se selecciona aleatoriamente con una distribución uniforme entre 1 y algún valor dado. La solución a este problema puede ser contraintuitiva, como la paradoja del cumpleaños.

Variantes y generalizaciones

La partición de igual cardinalidad es una variante en la que ambas partes deben tener un número igual de elementos, además de tener una suma igual. Esta variante también es NP-hard. ^[5]^: Demostración SP12 . Dada una instancia estándar de Partition con algunos números n , construya una instancia de Equal-Cardinality-Partition agregando n ceros. Claramente, la nueva instancia tiene una partición de igual cardinalidad y suma igual si y solo si la instancia original tiene una partición de igual suma. Consulte también Partición de números balanceada .

La partición del producto es el problema de dividir un conjunto de números enteros en dos conjuntos con el mismo producto (en lugar de la misma suma). Este problema es fuertemente NP-hard . ^[14]

Kovalyov y Pesch ^[15] analizan un enfoque genérico para demostrar la NP-dureza de los problemas de tipo partición.

Aplicaciones

Una aplicación del problema de la partición es la manipulación de elecciones . Supongamos que hay tres candidatos (A, B y C). Un único candidato debería ser elegido utilizando una regla de votación basada en la puntuación, por ejemplo, la regla del veto (cada votante veta a un único candidato y el candidato con menos vetos gana). Si una coalición quiere asegurarse de que C sea elegido, debería repartir sus votos entre A y B de modo de maximizar el menor número de vetos que cada uno de ellos obtenga. Si los votos están ponderados, entonces el problema puede reducirse al problema de la partición y, por lo tanto, puede resolverse de manera eficiente utilizando CKK. Lo mismo es cierto para cualquier otra regla de votación que se base en la puntuación. ^[16]

Notas

^ desde Korf 1998.
^ Hayes, Brian (marzo-abril de 2002), "El problema más fácil y difícil" (PDF) , American Scientist , vol. 90, núm. 2, Sigma Xi, The Scientific Research Society, págs. 113-117, JSTOR 27857621
^ Mertens 2006, pág. 125.
^ Korf, Richard E. (2009). Particionado de números multidireccional (PDF) . IJCAI .
^ ab Garey, Michael; Johnson, David (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . pp. 96–105. ISBN 978-0-7167-1045-5.
^ Goodrich, Michael. "Más problemas NP completos y NP difíciles" (PDF) .
^ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Problemas con la mochila. Saltador. pag. 97.ISBN 9783540402862.
^ Martello, Silvano; Toth, Paolo (1990). "Problema de la suma de 4 subconjuntos". Problemas de mochila: algoritmos e interpretaciones informáticas . Wiley-Interscience. págs. 105-136. ISBN 978-0-471-92420-3.Señor 1086874 .
^ Korf, Richard E. (20 de agosto de 1995). "De soluciones aproximadas a óptimas: un estudio de caso de partición de números". Actas de la 14.ª Conferencia conjunta internacional sobre inteligencia artificial . IJCAI'95. Vol. 1. Montreal, Quebec, Canadá: Morgan Kaufmann Publishers. págs. 266–272. ISBN 978-1-55860-363-9.
^ Gent y Walsh 1996.
^ Mertens 1998.
^ Mertens 2001, pág. 130.
^ Borgs, Chayes y Pittel 2001.
^ Ng, CT; Barketau, MS; Cheng, TCE; Kovalyov, Mikhail Y. (1 de diciembre de 2010). ""Partición de productos" y problemas relacionados con la programación y la fiabilidad de los sistemas: complejidad computacional y aproximación". Revista Europea de Investigación Operativa . 207 (2): 601–604. doi :10.1016/j.ejor.2010.05.034. ISSN 0377-2217.
^ Kovalyov, Mikhail Y.; Pesch, Erwin (28 de octubre de 2010). "Un enfoque genérico para demostrar la dureza NP de problemas de tipo partición". Matemáticas Aplicadas Discretas . 158 (17): 1908–1912. doi : 10.1016/j.dam.2010.08.001 . ISSN 0166-218X.
^ Walsh, Toby (11 de julio de 2009). "¿Dónde están los problemas de manipulación realmente difíciles? La transición de fase en la manipulación de la regla de veto" (PDF) . Escrito en Pasadena, California, EE. UU. Actas de la 21.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . San Francisco, California, EE. UU.: Morgan Kaufmann Publishers Inc., págs. 324–329. Archivado (PDF) desde el original el 10 de julio de 2020. Consultado el 5 de octubre de 2021 .

Referencias

Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), "Transición de fase y escalamiento de tamaño finito para el problema de partición de enteros", Random Structures and Algorithms , 19 (3–4): 247–288, CiteSeerX 10.1.1.89.9577 , doi :10.1002/rsa.10004, S2CID 6819493
Gent, Ian; Walsh, Toby (agosto de 1996). "Transiciones de fase y teorías anidadas: la partición de números como estudio de caso". En Wolfgang Wahlster (ed.). Actas de la 12.ª Conferencia Europea sobre Inteligencia Artificial . ECAI-96. John Wiley and Sons. págs. 170–174. CiteSeerX 10.1.1.2.4475 .
Gent, Ian; Walsh, Toby (1998), "Análisis de heurísticas para la partición de números", Computational Intelligence , 14 (3): 430–451, CiteSeerX 10.1.1.149.4980 , doi :10.1111/0824-7935.00069, S2CID 15344203
Korf, Richard E. (1998), "Un algoritmo completo en cualquier momento para la partición de números", Inteligencia artificial , 106 (2): 181–203, CiteSeerX 10.1.1.90.993 , doi :10.1016/S0004-3702(98)00086-1, ISSN 0004-3702
Mertens, Stephan (noviembre de 1998), "Transición de fase en el problema de partición de números", Physical Review Letters , 81 (20): 4281–4284, arXiv : cond-mat/9807077 , Bibcode :1998PhRvL..81.4281M, doi :10.1103/PhysRevLett.81.4281, S2CID 119541289
Mertens, Stephan (2001), "Un enfoque de un físico para la partición de números", Theoretical Computer Science , 265 (1–2): 79–108, arXiv : cond-mat/0009230 , doi :10.1016/S0304-3975(01)00153-0, S2CID 16534837
Mertens, Stephan (2006). "El problema más fácil y difícil: la partición de números". En Allon Percus; Gabriel Istrate; Cristopher Moore (eds.). Computational complex and statistical physics . Estados Unidos: Oxford University Press. págs. 125–140. arXiv : cond-mat/0310317 . Código Bibliográfico :2003cond.mat.10317M. ISBN 9780195177374.
Mertens, Stephan (1999), "Un algoritmo completo en cualquier momento para la partición equilibrada de números", arXiv : cs/9903011