Problema de partición

En teoría de números e informática, el problema de partición, o partición de números, es la tarea de decidir si un conjunto múltiple S dado de Los números enteros positivos se pueden 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".

Existe una versión de optimización del problema de partición, que consiste en dividir el conjunto múltiple S en dos subconjuntos S₁, S₂ tal que la diferencia entre la suma de elementos en S₁ y la suma de elementos en S₂ está minimizado. La versión de optimización es NP-hard, pero se puede resolver de forma eficaz en la práctica.

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

• En el problema de la suma del subconjunto, el objetivo es encontrar un subconjunto de S cuya suma es un determinado número de destino T dado como entrada (el problema de partición es el caso especial en el que T es la mitad de la suma S).
• En la partición multiway número, hay un parámetro entero k, y el objetivo es decidir si S se puede dividir en k subconjuntos de igual suma (el problema de la 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 ser |S|/3, donde cada subconjunto debe tiene 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.

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 duro. Esto se puede demostrar mediante la reducción del problema de la suma de subconjuntos. Una instancia de SubsetSum consta de un conjunto S de enteros positivos y una suma objetivo T; el objetivo es decidir si hay 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₁ y z₂, con z₁ = suma(S) y z₂ = 2T. La suma de este conjunto de entradas es sum(S) + z₁ + z₂ = 2 suma(S) + 2T, por lo que la suma objetivo para la partición es suma(S) + T.

• Supongamos que existe una solución S′ a la instancia SubsetSum. Entonces suma(S′) = T, so sum(S") ∪ ∪ {displaystyle cup } z_1) = sum(S) + T, entonces S. ∪ ∪ {displaystyle cup } z_1 es una solución al caso Partition.
• Por el contrario, suponga que existe una solución S′ a la instancia Partition. Entonces, S′′ debe contener z₁ o z₂, pero no ambos, ya que su suma es más que suma(S) + T. Si S' contiene z₁, entonces debe contener elementos de S con una suma de exactamente T, así que S' minus z₁ es una solución a la instancia SubsetSum. Si S' contiene z₂, entonces debe contener elementos de S con una suma de exactamente suma(S− T, así que los otros objetos en S son una solución a 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 de números de Greedy – bucles sobre los números, y pone cada número en el conjunto cuya suma actual es 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 a la mayoría 3/2 (" ratio 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 proporción de aproximación es a la mayoría 1+O()log⁡ ⁡ log⁡ ⁡ nn){displaystyle 1+Oleft({frac {log {log {n}{n}right)} casi seguro, y 1+O()1n){displaystyle 1+Oleft({frac {1}right)} en espera.
• Diferencia más grande Método (también llamado el algoritmo Karmarkar–Karp) clasifica los números en orden descendente y repetidamente reemplaza los números 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 – en la mayoría 7/6. Sin embargo, en el caso promedio se realiza mucho mejor que el algoritmo codicioso: cuando los números se distribuyen uniformemente en [0,1], su relación de aproximación es en la mayoría 1+1/n. . ()log⁡ ⁡ n){displaystyle 1+1/n^{ Theta (log {n}}} en espera. También funciona mejor en experimentos de simulación.
• El algoritmo multifit utiliza búsqueda binaria combinada con un algoritmo para el embalaje de bin. En el peor de los casos, su relación de aproximación es 8/7.
• El problema de la suma de subconjunto tiene un FPTAS que también se puede utilizar para el problema de la partición, estableciendo la suma de destino a la 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:

• El número de tiempo pseudopolynomial de partición toma O()nm){displaystyle O(nm)} memoria, donde m es el mayor número de la entrada.
• El Algoritmo completo de Greedy (CGA) considera todas las particiones construyendo un árbol binario. Cada nivel en el árbol corresponde a un número de entrada, donde la raíz corresponde al mayor número, el nivel inferior al siguiente número más grande, etc. Cada rama corresponde a un conjunto diferente en el que se puede poner el número actual. Traver el árbol en orden de profundidad primero requiere sólo O()n){displaystyle O(n)} espacio, pero podría tomar O()2n){displaystyle O(2^{n}} tiempo. El tiempo de ejecución se puede mejorar utilizando una heurística avaricia: en cada nivel, desarrollar primero la rama en la que el número actual se pone en el conjunto con la suma más pequeña. Este algoritmo encuentra primero la solución encontrada por la partición de números codiciosos, pero luego procede a buscar mejores soluciones. Algunas variaciones de esta idea son esquemas de aproximación totalmente polinomio-tiempo para el problema de subconjunto-sum, y por lo tanto para el problema de la partición también.
• El algoritmo completo de Karmarkar-Karp (CKK) considera todas las particiones construyendo 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. Funciona considerablemente más rápido que la CGA en casos aleatorios. Su ventaja es mucho mayor cuando existe una partición igual, y puede ser de varias órdenes de magnitud. En la práctica, los problemas de tamaño arbitrario pueden resolverse por CKK si los números tienen a la mayoría de 12 dígitos significativos. CKK también puede funcionar como un algoritmo en cualquier momento: encuentra la solución KK primero, y luego encuentra soluciones progresivamente mejores como el tiempo permite (posiblemente requerir tiempo exponencial para alcanzar la optimización, para las peores instancias). Requiere O()n){displaystyle O(n)} espacio, pero en el peor caso podría tomar O()2n){displaystyle O(2^{n}} tiempo.

Los algoritmos desarrollados para la suma de subconjuntos incluyen:

• Horowitz y Sanhi – corre en el tiempo O()2n/2⋅ ⋅ ()n/2)){displaystyle O(2^{n/2}cdot (n/2)}, pero requiere O()2n/2){displaystyle O(2^{n/2}} espacio.
• Schroeppel y Shamir – corre en el tiempo O()2n/2⋅ ⋅ ()n/4)){displaystyle O(2^{n/2}cdot (n/4)}, y requiere mucho menos espacio – O()2n/4){displaystyle O(2^{n/4}}.
• Howgrave-Graham y Joux – corre en el tiempo O()2n/3){displaystyle O(2^{n/3}}, pero es un algoritmo aleatorizado que sólo resuelve el problema de decisión (no el problema de optimización).

Instancias difíciles y transición de fase

Los conjuntos con solo una, o sin particiones tienden a ser más duros (o más caros) para 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, las particiones perfectas son más probables. Se sabe que el problema se somete a una "transición en fase"; es probable que sea para algunos conjuntos e improbable 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 <math alttext="{displaystyle m/nm/nc)1{displaystyle m/n won1}<img alt="{displaystyle m/n tiende a tener muchas soluciones y 1}" xmlns="http://www.w3.org/1998/Math/MathML">m/n■1{displaystyle m/n confidencial1}1}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert skin-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/713b2a6165d771e8242b7f647dcc9d137f8c5f87" style="vertical-align: -0.838ex; width:8.858ex; height:2.843ex;"/> 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 va a 1 o 0 respectivamente. This was originally argued based on empirical evidence by Gent and Walsh, then using methods from statistical physical by Mertens, and later demonstrated by Borgs, Chayes, and Pittel.

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 es aleatorio. seleccionado con distribución uniforme 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. Prueba. 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 y sólo si la instancia original tiene una partición de igual suma. Consulte también Partición de números equilibrados.

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.

Partición de 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.

Kovalyov y Pesch analizan un enfoque genérico para demostrar 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 un solo candidato utilizando una regla de votación basada en la puntuación, p. 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.