El problema de particionar un conjunto de números

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de octubre de 2021; la verificación requiere 1 edición .

El problema de dividir un conjunto de números es el problema de determinar si un multiconjunto dado S de enteros positivos se puede dividir en dos subconjuntos S 1 y S 2 de modo que la suma de los números de S 1 sea igual a la suma de los números de S 2 . Aunque el problema de partición de números es NP-completo , existe una solución temporal pseudopolinomial mediante programación dinámica y existen algoritmos heurísticos para resolver muchos problemas concretos de forma óptima o aproximada. Por esta razón, el problema se llama "el problema NP-difícil más simple" [1].

Existe una versión de optimización del problema de partición, en la que se requiere dividir el multiconjunto S en dos subconjuntos S 1 y S 2 , de modo que la diferencia entre la suma de los elementos de S 1 y la suma de los elementos de S 2 es mínimo. La versión de optimización es NP-hard , pero en la práctica se puede resolver de manera eficiente [2] .

Ejemplos

Dado un conjunto S ={3,1,1,2,2,1}, dos conjuntos S 1 ={1,1,1,2} y S 2 ={2,3} son una solución factible al problema de partición . Ambos conjuntos tienen suma 5 y son una partición de S . Tenga en cuenta que esta solución no es única. S 1 ={3,1,1} y S 2 ={2,2,1} es otra solución.

No todos los conjuntos múltiples de enteros positivos tienen una división en dos partes con sumas iguales. Un ejemplo de tal conjunto es S = {2,5}.

Algoritmo de tiempo pseudopolinomial

El problema se puede resolver mediante programación dinámica , siempre que el tamaño del conjunto y el tamaño de la suma de los números enteros en el conjunto no sean demasiado grandes para hacer inviables los requisitos de memoria.

Representemos la entrada del algoritmo como una lista de la forma:

S=x 1 , ..., x norte

Sea N el número de elementos del conjunto S. Sea K la suma de todos los elementos del conjunto S . Es decir, K = x 1 + ... + x n . Construiremos un algoritmo que determine si existe un subconjunto S cuya suma de elementos es igual a . Si el subconjunto existe, entonces:

si K es par, entonces el resto del conjunto S también da si K es impar, el resto del conjunto S dará la suma . Esta es la mejor solución posible.

Relaciones recurrentes

Queremos determinar si existe un subconjunto S cuya suma de elementos es . Dejar:

p ( i , j ) es True si hay un subconjunto entre { x 1 , ..., x j } cuyos elementos suman i y False en caso contrario.

Entonces p ( , n ) es Verdadero si y solo si existe un subconjunto de S cuya suma es . El objetivo de nuestro algoritmo es calcular p ( , n ). Para lograr esto, tenemos las siguientes fórmulas recurrentes :

p ( i , j ) es verdadero si p ( i , j − 1) es verdadero o p ( i − x j , j − 1) es verdadero p ( i , j ) se evalúa como False de lo contrario

La razón de esto es la siguiente: hay algún subconjunto S cuya suma es igual a i para los números

x 1 , ..., x j

si y solo si uno de los dos es verdadero:

hay un subconjunto { x 1 , ..., x j-1 } que da la suma i ; hay un subconjunto { x 1 , ..., x j-1 } que da la suma i − x j , ya que x j + la suma de este subconjunto = i .

Algoritmo pseudopolinomio

El algoritmo construye una tabla de tamaño n que contiene los valores de recurrencia, donde es la suma de los valores y es el número de elementos. Cuando toda la tabla esté llena, devuelve . A continuación se muestra la tabla P. En la figura, una flecha azul de un bloque a otro, si el valor del bloque final puede depender del valor del bloque de origen. Esta dependencia es una propiedad de una relación recursiva.

ENTRADA: Lista de enteros S SALIDA: Verdadero si S se puede dividir en dos subconjuntos que tienen las mismas sumas 1 función find_partition ( S ): 2n ← |S| 3 K ← sum(S) 4 P ← tabla booleana vacía de tamaño ( + 1) por (n + 1) 5 inicializa la fila superior ( P(0,x) ) de la tabla P a True 6 inicialice la columna más a la izquierda ( P(x, 0) ) de la tabla P , excepto la celda P(0, 0) a Falso 7 para i de 1 a 8 para j de 1 a n 9 si (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) o P(iS[j-1], j-1) 11 más 12 P(i, j) ← P(i, j-1) 13 regresar valor P( , n)

Ejemplo

A continuación se muestra la tabla P para el conjunto S ={3, 1, 1, 2, 2, 1} utilizado anteriormente:

Análisis

Este algoritmo se ejecuta en tiempo O ( KN ) , donde N es el número de elementos en el conjunto de entrada y K es la suma de los elementos en el conjunto de entrada.

El algoritmo se puede extender al problema multipartición de k partes, pero requiere O ( n ( k − 1) m k − 1 ) memoria , donde m es el número más grande en el conjunto de entrada, lo que hace que el algoritmo prácticamente no tenga sentido incluso para k = 3 , a menos que no se proporcionen números muy pequeños como entrada [2] .

Un caso especial del problema de la suma de subconjuntos

El problema de partición se puede considerar como un caso especial del problema de suma de subconjuntos, y la solución de programación dinámica de tiempo pseudopolinomial dada anteriormente se generaliza al problema de suma de subconjuntos .

Algoritmos de aproximación

Hay algunos algoritmos heurísticos para aproximar el problema de optimización de partición. Pueden extenderse a algoritmos de tiempo lineal exacto [2] .

Algoritmo codicioso

Un enfoque del problema, que imita la forma en que juega el hijo de un compañero, es un algoritmo codicioso que itera sobre los números en orden descendente y agrega cada número a una suma más pequeña. Este enfoque tiene un tiempo de ejecución O ( n log n ) . Este algoritmo heurístico funciona bien en la práctica si los números del conjunto son aproximadamente del mismo orden; sin embargo, no se garantiza que el algoritmo produzca la mejor partición posible. Por ejemplo, dado el conjunto S = {4, 5, 6, 7, 8} como entrada, este algoritmo codicioso daría como resultado una división de S en los subconjuntos {4, 5, 8} y {6, 7}. Sin embargo, S tiene una partición balanceada exacta en los subconjuntos {7, 8} y {4, 5, 6}.

Se sabe que este enfoque codicioso da una aproximación de 7 ⁄ 6 a la solución óptima de la versión de optimización. Es decir, si la salida del algoritmo voraz produce dos conjuntos A y B , entonces , donde OPT es el tamaño del conjunto más grande en la mejor partición [3] . A continuación se muestra un ejemplo (en Python ) de un algoritmo codicioso.

def find_partition ( int_list ): "Particionar `int_list` en dos conjuntos con sumas iguales" A = conjunto () B = conjunto () para n en ordenado ( int_list , reverse = True ): si suma ( A ) < suma ( B ) : A. _ añadir ( n ) más : B . sumar ( n ) devolver ( A , B )

El algoritmo se puede extender a casos de k > 2 conjuntos: elija los k elementos más grandes, distribúyalos en k conjuntos, luego itere sobre los números restantes en orden descendente y agréguelos al conjunto con una suma menor (la versión simple anterior corresponde k = 2 ) . Esta versión se ejecuta en tiempo O (2 k n 2 ) y se sabe que proporciona una aproximación [3] . Por lo tanto, tenemos un esquema de tiempo polinomial aproximado (PTAS) para el problema de partición, aunque no es un esquema de tiempo polinomial completamente aproximado (el tiempo de ejecución es exponencial para el nivel deseado de aproximación garantizada). Sin embargo, existen variantes de esta idea que son esquemas de tiempo polinomial completamente aproximados para el problema de suma de subconjuntos y, por lo tanto, también para el problema de partición [4] [5] .

Algoritmo de diferencia

Otra heurística es el método de la mayor diferencia (LDM) [6] , que se denomina heurística Karmarkar - Karp [2] en honor a los científicos que publicaron el método en 1982 [7] . El MNR tiene dos fases. La primera fase del algoritmo toma los dos números más grandes de la entrada y los reemplaza con la diferencia. Repita la operación hasta que quede un número. La sustitución representa una decisión de colocar dos números en diferentes subconjuntos, pero en qué conjuntos se colocan estos números, no se toma la decisión. Al final de la primera fase, el único número restante es la diferencia de las sumas de los dos subconjuntos. En la segunda etapa, se construye la solución real [1] .

El algoritmo heurístico de diferencia funciona mejor que el algoritmo voraz, pero sigue siendo pobre para problemas en los que los números dependen exponencialmente del tamaño del conjunto [1] .

El siguiente código Java representa la primera fase del algoritmo Karmarkar-Karp. El algoritmo usa el montón para encontrar eficientemente el par de números más grandes entre los restantes.

int karmarkarKarpPartition ( int [] baseArr ) { // crea el montón máximo PriorityQueue < Integer > heap = new PriorityQueue < Integer > ( baseArr . length , REVERSE_INT_CMP ); para ( valor int : baseArr ) { montón . agregar ( valor ); } while ( montón . tamaño ( ) > 1 ) { int val1 = montón . encuesta (); int val2 = montón . encuesta (); montón _ agregar ( val1 - val2 ); } montón de retorno . encuesta (); }

Otros enfoques

También hay algoritmos de corte de tiempo basados ​​en la heurística de diferencia que primero encuentran la solución obtenida por la heurística de diferencia, luego se encuentran progresivamente mejores soluciones si el tiempo lo permite ( es posible un crecimiento exponencial del tiempo de ejecución para obtener la solución óptima en el peor de los casos ). caso) [8] [9] .

Casos difíciles

Los conjuntos con una sola partición o sin particiones suelen ser los más difíciles (o los más derrochadores) para obtener una decisión sobre el tamaño de la entrada. Si los valores son pequeños en comparación con el tamaño del conjunto, es más probable que haya buenas particiones. Se sabe que el problema experimenta una " transición de fase " cuando las buenas particiones son más probables para algunos conjuntos e improbables 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 el problema con mayor frecuencia tiene muchas soluciones, y el problema con mayor frecuencia tiene una solución o ninguna solución. A medida que n y m aumentan, la probabilidad de una buena partición tiende a 1 y una mala partición a 0, respectivamente. Este hecho se basó inicialmente en los resultados empíricos de Gent y Walsh [10] , luego en los métodos de la física estadística (Mertens [11] [12] ) y, finalmente, el hecho fue probado por Borgs, Chayes y Pittel [13] .

Variantes y generalizaciones

Hay un problema sobre la partición en 3 de un conjunto de números , que busca una partición del conjunto S en | S |/3 triples, cada triple con la misma cantidad. Este problema es completamente diferente del problema de la partición y no tiene un algoritmo de tiempo de ejecución pseudopolinomial, a menos que P=NP [14] .

El problema de dividir en varios conjuntos generaliza la versión de optimización del problema de dividir. Aquí, el objetivo es dividir un conjunto o multiconjunto de n enteros en un número k de subconjuntos, minimizando la diferencia entre la suma más pequeña y más grande de números en los subconjuntos [2] .

Se pueden encontrar más generalizaciones del problema de partición en el documento " El problema de la creación de contenedores ".

Versión probabilística

Un problema relacionado, algo similar a la paradoja del cumpleaños , es encontrar un tamaño de conjunto de entrada para el cual la probabilidad de existencia de una solución sea 0,5, dado que cada elemento del conjunto se elige aleatoriamente entre 1 y algún valor dado.

La solución a este problema puede resultar paradójica. Por ejemplo, al elegir aleatoriamente números enteros entre 1 y un millón, muchas personas piensan que la respuesta será miles, decenas de miles o incluso cientos de miles, cuando en realidad, la respuesta correcta será alrededor de 23 (para más detalles, consulte el artículo Problema de partición ).

Notas

  1. ↑ 123 Hayes , 2002 .
  2. ↑ 1 2 3 4 5 Korf, 2009 .
  3. ↑ 1 2 Graham, 1969 , pág. 416–429.
  4. ↑ Kellerer, Pferschy, Pisinger, 2004 , pág. 94.
  5. ↑ Martello, Toth, 1990 , pág. 105–136.
  6. ↑ Michiels, Korst, Aarts, 2003 , pág. 71–75.
  7. ↑ Karmarkar, Karp, 1982 .
  8. ↑ Korff, 1998 .
  9. ↑ Mertens, 1999 .
  10. ↑ Gent, Walsh, 1996 .
  11. ↑ Mertens, 1998 .
  12. ↑ Mertens, 2001 .
  13. ↑ Borgs, Chayes, Pittel, 2001 .
  14. ↑ Garey y Johnson 1979 , pág. 96–105.

Literatura