Partición de números de tiempo pseudopolinomiales

En ciencias de la computación , la partición de números en tiempo pseudopolinomial es un algoritmo de tiempo pseudopolinomial para resolver el problema de partición .

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

Supongamos que la entrada al algoritmo es un multiconjunto de cardinalidad : ${\displaystyle S}$ ${\displaystyle N}$

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

Sea K la suma de todos los elementos de S . Es decir: K = x ₁ + ... + x _N . Construiremos un algoritmo que determine si existe un subconjunto de S cuya suma sea . Si existe un subconjunto, entonces: ${\displaystyle \lfloor K/2\rfloor }$

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 . Esta es la mejor solución posible. ${\displaystyle \lceil K/2\rceil }$

eg1 S = {1, 2, 3, 5}, K = suma(S) = 11, K/2 = 5, Encuentra un subconjunto de S que sea más cercano a K/2 -> {2, 3} = 5, 11 - 5 * 2 = 1

eg2 S = {1, 3, 7}, K = suma(S) = 11, K/2 = 5, Encuentra un subconjunto de S que sea más cercano a K/2 -> {1, 3} = 4, 11 - 4 * 2 = 3

Relación de recurrencia

Queremos determinar si existe un subconjunto de S cuya suma sea . Sea: ${\displaystyle \lfloor K/2\rfloor }$

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

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

p ( i , j ) es Verdadero si p ( i , j − 1) es Verdadero o si p ( i − x _j , j − 1) es Verdadero

p ( i , j ) es falso en caso contrario

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

x ₁ , ..., x _j

si y sólo si se cumple cualquiera de las siguientes condiciones:

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

hay un subconjunto de { x ₁ , ..., x _{j −1} } cuya suma es i − x _j , ya que x _j + la suma de ese subconjunto = i .

El algoritmo pseudopolinomial

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

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

La función can_be_partitioned_equally( S ) tiene  como entrada: una lista de números enteros S . Salida: Verdadero si S se puede dividir en dos subconjuntos que tienen una suma igual. n ← |S| K ← suma( S ) P ← tabla booleana vacía de tamaño ( + 1) ${\displaystyle \lfloor K/2\rfloor }$ por (n + 1) inicializar la fila superior ( P (0, x )) de P a Verdadero inicializar la columna más a la izquierda ( P ( x , 0)) de P , excepto P (0, 0) a Falso para  i  de 1 a  para j de 1 a n x = S [ j -1] si ( i - x ) >= 0 entonces P ( i , j ) ← P ( i , j -1) o P ( i - x , j -1) de lo contrario P ( i , j ) ← P ( i , j -1) ${\displaystyle \lfloor K/2\rfloor }$       devuelve  P ( , n ) ${\displaystyle \lfloor K/2\rfloor }$

Ejemplo

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

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

Análisis

Este algoritmo se ejecuta en un 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 al problema de particionamiento múltiple de k vías, pero entonces requiere O ( n ( k − 1) m ^{k − 1} ) de memoria donde m es el número más grande en la entrada, lo que lo hace poco práctico incluso para k = 3 a menos que las entradas sean números muy pequeños. ^[1]

Este algoritmo se puede generalizar a una solución para el problema de suma de subconjuntos .

Referencias

1. Korf, Richard E. (2009). Particionado de números multidireccional (PDF) . IJCAI .