LISTA DE PROBLEMAS

La coincidencia numérica tridimensional es un problema de decisión de NP completo . Está dado por tres conjuntos múltiples de enteros $${\ displaystyle X}, $${\ displaystyle Y} y $${\ displaystyle Z}, cada uno con $${\ displaystyle k} elementos y un límite $${\ displaystyle b}. El objetivo es seleccionar un subconjunto$${\ displaystyle M} de $${\ displaystyle X \ times Y \ times Z} tal que cada entero en $${\ displaystyle X}, $${\ displaystyle Y} y $${\ displaystyle Z} ocurre exactamente una vez y eso por cada triple $${\ displaystyle (x, y, z)} en el subconjunto $${\ displaystyle x + y + z = b}sostiene. Este problema está etiquetado como [SP16] en. 

Ejemplo [ editar ]

Tomar $${\ displaystyle X = \ {3,4,4 \}}, $${\ displaystyle Y = \ {1,4,6 \}} y $${\ displaystyle Z = \ {1,2,5 \}}y $${\ displaystyle b = 10}. Esta instancia tiene una solución, a saber$${\ displaystyle \ {(3,6,1), (4,4,2), (4,1,5) \}}. Tenga en cuenta que cada triple suma a$${\ displaystyle b = 10}. El conjunto$${\ displaystyle \ {(3,6,1), (3,4,2), (4,1,5) \}} no es una solución por varias razones: no se utilizan todos los números (un $${\ displaystyle 4 \ en X} falta), se usa un número con demasiada frecuencia (el $${\ displaystyle 3 \ en X}) y no todas las sumas triples a $${\ displaystyle b} (ya que $${\ displaystyle 3 + 4 + 2 = 9 \ neq b = 10}) Sin embargo, hay al menos una solución a este problema, que es la propiedad que nos interesa con los problemas de decisión. Si tomáramos$${\ displaystyle b = 11} por lo mismo $${\ displaystyle X}, $${\ displaystyle Y} y $${\ displaystyle Z}, este problema no tendría solución (todos los números suman $${\ displaystyle 30}, que no es igual a $${\ displaystyle k \ cdot b = 33} en este caso).

Problemas relacionados [ editar ]

Cada instancia del problema numérico de coincidencia tridimensional es una instancia tanto del problema de 3 particiones como del problema de coincidencia tridimensional.

Prueba de integridad de NP [ editar ]

La integridad de NP del problema de 3 particiones es declarada por Garey y Johnson en "Computers and Intractability; A Guide to the Theory of NP-Completeness", que hace referencia a este problema con el código [SP16]. ^[1] Se realiza mediante una reducción del emparejamiento tridimensional a través de 4 particiones. Para demostrar la completitud NP del emparejamiento numérico tridimensional, la prueba es similar, pero se debe usar una reducción del emparejamiento tridimensional mediante el problema del emparejamiento numérico 4-dimensional.

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 conjunto múltiple S dado de enteros positivos se puede dividir en dos subconjuntos S ₁ y S _{2 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 la partición es NP-completo , hay una programación dinámica de tiempo pseudo-polinomial solución, y hay heurísticas que resuelven el problema en muchos casos, de manera óptima o aproximadamente. Por esta razón, se le ha llamado "el problema NP-hard más fácil". ^[2]

Existe una versión de optimización del problema de partición, que consiste en dividir el multiset S en dos subconjuntos S ₁ , S _{2 de} modo que la diferencia entre la suma de elementos en S ₁ y la suma de elementos en S ₂ se minimice. La versión de optimización es NP-hard , pero puede resolverse eficientemente en la práctica.

Ejemplos [ editar ]

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 particionan 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 enteros positivos tienen una partición en dos subconjuntos con la misma suma. Un ejemplo de tal conjunto es S = {2,5}.

Algoritmo de tiempo pseudo-polinomial [ editar ]

El problema puede resolverse mediante programación dinámica cuando el tamaño del conjunto y el tamaño de la suma de los enteros en el conjunto no son demasiado grandes para que los requisitos de almacenamiento no sean factibles.

Supongamos que la entrada al algoritmo es un conjunto múltiple $${\ displaystyle S} de cardinalidad $${\ displaystyle N}:

S = { x ₁ , ..., x _N }

Deje que K sea la suma de todos los elementos en S . Esto es: K = x ₁ + ... + x _N . Construiremos un algoritmo que determine si hay un subconjunto de S que sume a$${\ displaystyle \ lfloor K / 2 \ rfloor}. Si hay un subconjunto, entonces:

si K es par, el resto de S también suma$${\ displaystyle \ lfloor K / 2 \ rfloor}

si K es impar, entonces el resto de S suma a$${\ displaystyle \ lceil K / 2 \ rceil}. Esta es la mejor solución posible.

Relación de recurrencia [ editar ]

Deseamos determinar si hay un subconjunto de S que sume a$${\ displaystyle \ lfloor K / 2 \ rfloor}. Dejar:

p ( i , j ) sea verdadero si un subconjunto de { x ₁ , ..., x _j } suma i y falso en caso contrario.

Entonces p ($${\ displaystyle \ lfloor K / 2 \ rfloor}, N ) es Verdadero si y solo si hay un subconjunto de S que suma$${\ displaystyle \ lfloor K / 2 \ rfloor}. El objetivo de nuestro algoritmo será calcular p ($${\ displaystyle \ lfloor K / 2 \ rfloor}, N ). En ayuda de esto, tenemos la siguiente relación de recurrencia :

p ( i , j ) es True si p ( i , j - 1) es True o si p ( i - x _j , j - 1) es True

p ( i , j ) es falso de lo contrario

El razonamiento para esto es el siguiente: hay un subconjunto de S que suma a i usando números

x ₁ , ..., x _j

si y solo si alguno de los siguientes es verdadero:

Hay un subconjunto de { x ₁ , ..., x _j −1 } que suma i ;

hay un subconjunto de { x ₁ , ..., x _j −1 } que suma i - x _j , ya que x _j + suma de ese subconjunto = i .

El algoritmo pseudo-polinomial [ editar ]

El algoritmo consiste en construir una tabla de tamaño $${\ displaystyle \ lfloor K / 2 \ rfloor} por $${\ displaystyle N}que contiene los valores de la recurrencia. Recuerda eso$${\ displaystyle K} es la suma de todos $${\ displaystyle N} elementos en $${\ displaystyle S}. Una vez que toda la tabla está llena, regresamos$${\ displaystyle P (\ lfloor K / 2 \ rfloor, N)}. A continuación se muestra una representación de la tabla.$${\ displaystyle P}. Hay una flecha azul de un bloque a otro si el valor del bloque objetivo puede depender del valor del bloque fuente. Esta dependencia es una propiedad de la relación de recurrencia.

Dependencias de la entrada de la tabla ( i , j )

función find_partition ( S ) es 
    de entrada: Una lista de los números enteros S .
    salida: Verdadero si S puede dividirse en dos subconjuntos que tienen la misma suma.

    n ← | S |
    K ← suma ( S )
     P ← tabla booleana vacía de tamaño ($${\ displaystyle \ lfloor K / 2 \ rfloor}
  
+ 1) por (n + 1)

    inicializar fila superior ( P (0, x )) de P en True
     initialize más a la izquierda en columna ( P ( x , 0)) de P , a excepción de P (0, 0) en False

    para  i  de 1 a $${\ displaystyle \ lfloor K / 2 \ rfloor}
  

        para  j  de 1 a n
             si ( i - S [ j ])> = 0 entonces 
                P ( i , j ) ← P ( i , j -1) o  P ( i - S [ j ], j -1)
             más 
                P ( i , j ) ← P ( i , j -1)

   devolver  P ($${\ displaystyle \ lfloor K / 2 \ rfloor}
  
, n )

Ejemplo [ editar ]

A continuación se muestra la tabla de P para el ejemplo de conjunto utilizado más arriba S = {3, 1, 1, 2, 2, 1}:

Resultado de la ejecución del algoritmo de ejemplo en la tabla P

Análisis [ editar ]

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

El algoritmo se puede extender a la k -WAY problema de múltiples particiones, pero luego toma O ( n ( k - 1) m ^{k - 1} ) de memoria donde m es el número más grande en la entrada, por lo que es poco práctico incluso para k = 3 a menos que las entradas sean números muy pequeños. ^[3]

Caso especial del problema de suma de subconjuntos [ editar ]

El problema de partición puede verse como un caso especial del problema de suma de subconjuntos y la solución de programación dinámica de tiempo pseudopolinomial dada anteriormente generaliza a una solución para el problema de suma de subconjuntos .

Aproximación del algoritmo de aproximación [ editar ]

Existen varios algoritmos heurísticos para producir aproximaciones al problema de optimización de la partición. Estos pueden extenderse a algoritmos exactos de espacio lineal . ^[3]

El algoritmo codicioso [ editar ]

Un enfoque del problema, que imita la forma en que los niños eligen equipos para un juego, es el algoritmo codicioso , que itera a través de los números en orden descendente, asignando a cada uno de ellos el subconjunto que tenga la suma más pequeña. Este enfoque tiene un tiempo de ejecución de O ( n log n ) . Esta heurística funciona bien en la práctica cuando los números en el conjunto son aproximadamente del mismo tamaño que su cardinalidad o menos, pero no se garantiza que produzca la mejor partición posible. Por ejemplo, dado el conjunto S = {4, 5, 6, 7, 8} como entrada, este algoritmo codicioso dividiría S en los subconjuntos {4, 5, 8} y {6, 7}; sin embargo, S tiene una partición exactamente equilibrada en subconjuntos {7, 8} y {4, 5, 6}.

Este enfoque codicioso es conocido por dar un ⁷ / ₆ - aproximación a la solución óptima de la versión optimización; es decir, si el algoritmo codicioso salidas dos conjuntos A y B , a continuación, max (s A, ΣB) ≤ 7/6 OPT , donde OPT es el tamaño del conjunto más grande en la mejor partición posible. ^[4] A continuación se ofrece un ejemplo (escrito en Python ) para el algoritmo codicioso.

def  find_partition ( números ): 
    "" "Separe los números dados en dos series de suma igual. 
    Args: 
        números: una colección de números, por ejemplo, una lista de enteros. 
    Devuelve: 
        dos listas de números. 
    " "" 
    A  =  [] 
    B  =  [] 
    sum_A  =  0 
    sum_B  =  0 
    para  n  en  ordenados ( int_list ,  revertir = Verdadero ): 
        si  sum_A  <  sum_B : 
           a . agregar (n ) 
           sum_A  =  sum_A  +  n 
        otra cosa : 
           B . agregar ( n ) 
           sum_B  =  sum_B  +  n 
    return  ( A ,  B )

Este algoritmo puede extenderse al caso de k > 2 conjuntos: para tomar los k elementos más grandes, y para cada partición de ellos, extiende la partición agregando los elementos restantes sucesivamente a cualquier conjunto que sea más pequeño. (La versión simple anterior corresponde a k = 2 ). Esta versión se ejecuta en tiempo O (2 ^k n ² ) y es conocido para dar un 4/3 - 1/3 k aproximación. ^[4] Entonces, tenemos un esquema de aproximación de tiempo polinómico (PTAS) para el problema de partición de números, aunque esto no es unesquema de aproximación de tiempo completamente polinomial (el tiempo de ejecución es exponencial en la garantía de aproximación deseada). Sin embargo, hay variaciones de esta idea que son esquemas de aproximación de tiempo completamente polinomial para el problema de suma de subconjuntos y, por lo tanto, también para el problema de partición. ^[5] [6]

Algoritmo de diferenciación [ editar ]

Otra heurística es el método de diferenciación más grande (LDM), ^[7] también llamado Karmarkar - Karp heuristic ^[3] después del par de científicos que lo publicó en 1982. ^[8] LDM opera en dos fases. La primera fase del algoritmo toma los dos números más grandes de la entrada y los reemplaza por su diferencia; esto se repite hasta que solo quede un número. El reemplazo representa la decisión de colocar los dos números en conjuntos diferentes, sin decidir de inmediato cuál está en qué conjunto. Al final de la fase uno, el único número restante es la diferencia de las dos sumas de subconjuntos. La segunda fase reconstruye la solución real. ^[2]

La heurística de diferenciación funciona mejor que la codiciosa, pero sigue siendo mala para los casos en que los números son exponenciales en el tamaño del conjunto. ^[2]

El siguiente código Java implementa la primera fase de Karmarkar – Karp. Utiliza un montón para encontrar eficientemente el par de números restantes más grandes.

int  karmarkarKarpPartition ( int []  baseArr )  { 	
    // crea el montón máximo	 
    PriorityQueue < Integer >  heap  =  new  PriorityQueue < Integer > ( baseArr . length ,  REVERSE_INT_CMP );

    for  ( int  value  :  baseArr )  { 		
        heap . agregar ( valor ); 	
    }

    while ( heap . size ()  >  1 )  { 
        int  val1  =  heap . encuesta (); 	
        int  val2  =  montón . sondear (); 	
        montón . agregar ( val1  -  val2 ); 
    }

    volver  montón . encuesta (); 
}

Otros enfoques [ editar ]

También hay algoritmos en cualquier momento , basados ​​en la heurística de diferenciación, que primero encuentran la solución devuelta por la heurística de diferenciación, luego encuentran soluciones progresivamente mejores según lo permita el tiempo (posiblemente requiera un tiempo exponencial para alcanzar la óptima, en el peor de los casos). ^[9]

Instancias difíciles [ editar ]

Los conjuntos con solo una o sin particiones tienden a ser 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, las particiones perfectas son más probables. Se sabe que el problema sufre una " transición de fase "; siendo probable que para algunos conjuntos y es poco probable para los demás. Si m es el número de bits necesarios para expresar cualquier número en el conjunto yn es el tamaño del conjunto, entonces{\ displaystyle m / n <1 font=""> tiende a tener muchas soluciones y {\ displaystyle m / n> 1}tiende a tener pocas o ninguna solución. A medida que nym aumentan, la probabilidad de una partición perfecta va a 1 o 0 respectivamente. Originalmente, esto fue argumentado en base a la evidencia empírica de Gent y Walsh, ^[10] luego utilizando métodos de física estadística de Mertens, ^[11] y luego probado por Borgs , Chayes y Pittel . ^[12]

Variantes y generalizaciones [ editar ]

La restricción de requerir que la partición tenga el mismo tamaño, o que todos los enteros de entrada sean distintos, también es NP-hard. ^{[ cita requerida ]}

Hay un problema llamado problema de 3 particiones que consiste en particionar el conjunto S en | S | / 3 se triplica cada uno con la misma suma. Este problema es bastante diferente al problema de la partición y no tiene un algoritmo de tiempo pseudo-polinomial a menos que P = NP . ^[13]

El problema de partición multidireccional generaliza la versión de optimización del problema de partición. Aquí, el objetivo es dividir un conjunto o conjunto múltiple de n enteros en un número dado k de subconjuntos, minimizando la diferencia entre las sumas de subconjunto más pequeñas y más grandes. ^[3]

Versión probabilística [ editar ]

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

La solución a este problema puede ser contra intuitiva, como la paradoja del cumpleaños.