problema de partición

En teoría de números e informática , el problema de partición , o partición de números , ^[1] es la tarea de decidir si un conjunto múltiple S dado de enteros positivos se puede dividir en dos subconjuntos S ₁ y S ₂ de modo que la suma de los números en S ₁ es 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 existen heurísticas que resuelven el problema en muchos casos, ya sea de manera óptima o aproximada. Por esta razón, se le ha llamado "el problema difícil más fácil". ^[2]^[3]

Existe una versión de optimización del problema de partición, que consiste en dividir el multiconjunto _S_endos subconjuntos S1 , _S2 de modo que se minimice la diferencia entre la suma de _{elementos en}S1 y la suma de elementos en S2 . La versión de optimización 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 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 de múltiples vías , hay un parámetro entero k , y el objetivo es decidir si S puede dividirse en k subconjuntos de igual suma (el problema de partición es el caso especial en el que k = 2).

Sin embargo, es bastante diferente al problema de las 3 particiones : en ese problema, el número de subconjuntos no está fijado de antemano; debería estarlo | S |/3, donde cada subconjunto debe tener exactamente 3 elementos. La partición 3 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 al problema de partición son los dos conjuntos S ₁ = {1,1,1,2} y S ₂ = {2,3}. Ambos conjuntos suman 5 y dividen S . Tenga en cuenta que esta solución no es única. S ₁ = {3,1,1} y S ₂ = {2,2,1} es otra solución.

No todos los conjuntos múltiples de números enteros positivos tienen una partición en dos subconjuntos con suma igual. Un ejemplo de tal conjunto es S = {2,5}.

Dureza computacional

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

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

Supongamos que existe una solución S ′ para la instancia de SubsetSum. Entonces sum( S ′) = T , entonces sum(S′ z_1) = sum( S ) + T , entonces S ′ z_1 es una solución para la instancia de Partición. $\taza$ $\taza$
Por el contrario, supongamos que existe una solución S " para la instancia de Partición. Entonces, S " debe contener z ₁ o z ₂ , pero no ambos, ya que su suma es mayor que suma( 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 tanto, puede resolverse mediante algoritmos desarrollados para cada uno de estos problemas. Los algoritmos desarrollados para la partición de números de múltiples vías incluyen:

Partición codiciosa de números : recorre los números y coloca cada número en el conjunto cuya suma actual es la más pequeña. Si los números no están ordenados, entonces el tiempo de ejecución es O( n ) y la relación de aproximación es como máximo 3/2 ("relación de aproximación" significa la suma mayor en la salida del algoritmo, dividida por la suma mayor en una partición óptima). Ordenar los números aumenta el tiempo de ejecución a O ( n log n ) y mejora la relación de aproximación a 7/6. Si los números se distribuyen uniformemente en [0,1], entonces la relación de aproximación es, como máximo , casi segura yesperada. $1+O\left({\frac {\log {\log {n}}}{n}}\right)$ $1+O\left({\frac {1}{n}}\right)$
El método de diferenciación más grande (también llamado algoritmo de Karmarkar-Karp ) ordena los números en orden descendente y los reemplaza repetidamente por sus diferencias. La complejidad del tiempo de ejecución es O ( n log n ). En el peor de los casos, su relación de aproximación es similar: como máximo 7/6 . Sin embargo, en el caso promedio funciona mucho mejor que el algoritmo codicioso: cuando los números se distribuyen uniformemente en [0,1], su relación de aproximación es, como máximo, laesperada. También funciona mejor en experimentos de simulación. $1+1/n^{\Theta (\log {n})}$
El algoritmo Multifit utiliza búsqueda binaria combinada con un algoritmo para empaquetar contenedores . En el peor de los casos, su relación de aproximación es 8/7 .
El problema de suma de subconjuntos tiene un FPTAS que también se puede utilizar 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-difícil, tales algoritmos pueden tomar un tiempo exponencial en general, pero pueden ser prácticamente utilizables en ciertos casos. Los algoritmos desarrollados para la partición de números de múltiples vías incluyen:

La partición de números de tiempo pseudopolinomial requiere memoria, donde $m$ es el número más grande en la entrada. $O(nm)$
El algoritmo codicioso completo (CGA) considera todas las particiones mediante la construcción de un árbol binario . Cada nivel en el á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. Atravesar el árbol en primer orden en profundidad solo requiere espacio, pero puede llevar tiempo. El tiempo de ejecución se puede mejorar usando una heurística codiciosa: en cada nivel, desarrolle 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 mediante la partición de números codiciosos , pero luego procede a buscar mejores soluciones. Algunas variaciones de esta idea son esquemas de aproximación en tiempo totalmente polinomial para el problema de suma de subconjuntos y, por tanto, también para el problema de partición. ^[7]^[8] $O(n)$ $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 mediante 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, CKK puede resolver problemas de tamaño arbitrario si los números tienen como máximo 12 dígitos significativos . ^[9] CKK también puede ejecutarse como un algoritmo en cualquier momento : primero encuentra la solución KK y luego encuentra soluciones progresivamente mejores a medida que el tiempo lo permite (posiblemente requiriendo un tiempo exponencial para alcanzar la optimización, en los peores casos). ^[1] Requiere espacio, pero en el peor de los casos puede llevar tiempo. $O(n)$ $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))$ $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). $O(2^{n/3})$

Instancias difíciles y transición de fase.

Los conjuntos con una sola partición o ninguna partición tienden a ser los más difíciles (o más caros) 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 produzcan particiones perfectas. Se sabe que el problema sufre una " transición de fase "; siendo probable para algunos conjuntos e improbable para otros. Si m es el número de bits necesarios para expresar cualquier número del 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 aumentan, la probabilidad de una partición perfecta pasa a 1 o 0 respectivamente. Esto fue argumentado originalmente basándose en evidencia empírica por Gent y Walsh, ^[10] luego usando métodos de la física estadística por Mertens, ^[11]^[12] y luego demostrado por Borgs , Chayes y Pittel. ^[13] $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 haya una solución, bajo el supuesto de que cada elemento del conjunto se selecciona aleatoriamente con métodos uniformes. distribución entre 1 y algún valor dado. La solución a este problema puede ser contraria a la intuición, 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 igual número de ítems, además de tener igual suma. Esta variante también es NP-duro. ^[5]^: Prueba SP12 . Dada una instancia de partición estándar con algunos n números, construya una instancia de partición de igual cardinalidad agregando n ceros. Claramente, la nueva instancia tiene una partición de igual cardinalidad y suma igual si la instancia original tiene una partición de igual suma. Consulte también Partición de números equilibrados .

La partición distinta es una variante en la que todos los números enteros de entrada son distintos. Esta variante también es NP-duro. ^{[ cita necesaria ]}

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-difícil . ^[14]

Kovalyov y Pesch ^[15] discuten un enfoque genérico para probar la dureza NP de 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). Se debe elegir a un solo candidato utilizando una regla de votación basada en la puntuación, por ejemplo, la regla del veto (cada votante veta a un solo candidato y gana el candidato con menos vetos). Si una coalición quiere asegurarse de que C sea elegido, debe dividir sus votos entre A y B para maximizar el menor número de vetos que obtenga cada uno de ellos. Si los votos son ponderados, entonces el problema puede reducirse al problema de partición y, por lo tanto, puede resolverse de manera eficiente utilizando CKK. Lo mismo se aplica a cualquier otra regla de votación que se base en la puntuación. ^[dieciséis]

Notas

^ ab Korf 1998.
^ Hayes, Brian (marzo-abril de 2002), "El problema difícil más fácil" (PDF) , American Scientist , vol. 90, núm. 2, Sigma Xi, Sociedad de Investigación Científica, págs. 113–117, JSTOR 27857621
^ Mertens 2006, pag. 125.
^ Korf, Richard E. (2009). Partición de números multidireccional (PDF) . IJCAI .
^ ab Garey, Michael; Johnson, David (1979). Computadoras e Intratabilidad; Una guía para la teoría de la integridad NP . págs. 96-105. ISBN 978-0-7167-1045-5.
^ Goodrich, Michael. "Más problemas de 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). "4 Problema de suma de 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 Internacional Conjunta sobre Inteligencia Artificial . IJCAI'95. vol. 1. Montreal, Quebec, Canadá: Morgan Kaufmann Publishers. págs. 266–272. ISBN 978-1-55860-363-9.
^ Caballero y Walsh 1996.
^ Mertens 1998.
^ Mertens 2001, pag. 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 de programación y confiabilidad de 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 de partición". Matemática Aplicada Discreta . 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, Estados Unidos. Actas de la XXI Conferencia Internacional Conjunta 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, cristiano; Chayés, Jennifer; Pittel, Boris (2001), "Transición de fase y escalado de tamaño finito para el problema de partición de enteros", Algoritmos y estructuras aleatorias , 19 (3–4): 247–288, CiteSeerX 10.1.1.89.9577 , doi :10.1002/rsa .10004, S2CID 6819493
Caballero, Ian; Walsh, Toby (agosto de 1996). "Transiciones de fase y teorías recocidas: partición de números como estudio de caso". En Wolfgang Wahlster (ed.). Actas de la XII Conferencia Europea sobre Inteligencia Artificial . ECAI-96. John Wiley e hijos. págs. 170-174. CiteSeerX 10.1.1.2.4475 .
Caballero, Ian; Walsh, Toby (1998), "Análisis de heurística para la partición de números", Inteligencia computacional , 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), "El enfoque de un físico para la partición de números", Ciencias de la Computación Teórica , 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 sencillo y difícil: la partición de números". En Allon Percus; Gabriel Istrate; Cristopher Moore (eds.). Complejidad computacional y física estadística . 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