, presentaré una solución al problema de la suma de subconjuntos, que tiene una complejidad de tiempo lineal O(n), si todos los 'n' valores de entrada están "lo suficientemente cerca" entre sí. En breve veremos qué significa realmente esa condición, así como por qué a menudo puede mantenerse (o casi mantenerse) en la práctica. Para las entradas que están "casi cercanas" entre sí, el algoritmo todavía tiene una cierta probabilidad de funcionar lo suficientemente rápido.
Este artículo está organizado de la siguiente manera:
En el capítulo 1, recordaremos el problema de la suma de subconjuntos y mostraremos probablemente la solución más trivial, basada en la técnica de la fuerza bruta. El Capítulo 2 recuerda la clase de problemas NP-completos y cómo se relaciona con ella el problema de suma de subconjuntos. El Capítulo 3 revisa la solución comúnmente utilizada basada en la técnica de programación dinámica y destaca por qué es un algoritmo pseudopolinomial. En el capítulo 4, presentaré el nuevo algoritmo, llamado "Solución basada en intervalos". El Capítulo 5 mostrará que, de manera similar a la técnica de programación dinámica, el algoritmo basado en intervalos también puede restaurar el subconjunto exacto de elementos que forman la suma objetivo dada, y no solo responder si la suma objetivo es alcanzable o no. Finalmente, en el capítulo 6, veremos por qué el algoritmo basado en intervalos realmente alcanza una complejidad de tiempo lineal, si todos los 'n' valores de entrada están lo suficientemente cerca entre sí (y también entenderemos allí qué significa realmente la condición "suficientemente cerca").
1. Recordando el problema de la suma de subconjuntos
La definición del problema de suma de subconjuntos (SSP) es bastante simple:
Se nos dan 'n' enteros de entrada X={x1, x2,…, xn} y una suma objetivo 'q'. Es necesario averiguar si existe tal subconjunto 'Y' de esos 'n' enteros, cuyos números sumarán exactamente 'q'. Si es así, es posible que el problema también solicite informar todos los números del subconjunto 'Y'.
A continuación se muestra un ejemplo de entrada al SSP:
La suma objetivo 'q=22' se muestra a la izquierda.
Y aquí está su solución:
Tenga en cuenta que puede haber casos con más de una solución, para una suma objetivo determinada 'q':
Además, puede haber casos en los que no haya ninguna solución, lo que significa que no existe tal subconjunto, cuyos números enteros se acumularán exactamente hasta la suma objetivo dada 'q':
En este artículo, consideraremos solo valores de entrada positivos xi ∈ X. Sin embargo, todas las ideas que se presentarán a continuación se pueden aplicar (con modificaciones menores) también al caso en que también haya valores de entrada negativos.
En el problema de suma de subconjuntos (SSP), un ligero cambio en los valores de entrada puede llevar a un cambio completo de la respuesta. Por ejemplo, si hay muchos subconjuntos que forman la suma objetivo 'q', no significa que habrá incluso un subconjunto que forme la suma objetivo 'q+1'. Este hecho también hace que el SSP no sea fácil de resolver.
Incluso cuando no hay muchos números de entrada, puede resultar difícil resolver el problema en una hoja de papel. A menudo, necesitaremos considerar todos los subconjuntos diferentes y comprobar cuál de ellos se acumula hacia 'q'. Ese enfoque reside en la solución trivial de SSP, la fuerza bruta, que simplemente enumera todos los subconjuntos posibles.
La idea para la implementación de fuerza bruta es: considerando que existe un subconjunto Y⊆X, cuyos elementos se acumulan hacia 'q', abordemos el último elemento de entrada xn. Hay dos escenarios:
O xn participa en el subconjunto de resultados 'Y' o no.
Dicho esto, si xn participa en 'Y' (xn∈Y), entonces deberíamos continuar buscando dicho subconjunto del conjunto reducido de números “X {xn} = {x1, x2,…, xn-1}”, que se acumulará ahora en “q–xn”:
Entonces, a partir de los números restantes, debemos construir la suma “22-6=16”.
De lo contrario, si el caso es que xn no participa en 'Y' (xn∉Y), entonces deberíamos continuar buscando dicho subconjunto del conjunto reducido de números “X {xn} = {x1, x2, …, xn-1}”, que a su vez se acumulará hasta la misma suma objetivo 'q':
Entonces, a partir de los números restantes, debemos construir la misma suma “22”.
Seguramente no sabemos de antemano cuál es el caso; es por eso que el algoritmo de fuerza bruta simplemente prueba un caso tras otro.
Al intentar resolver el problema reducido (es decir, encontrar un subconjunto adecuado del conjunto reducido de números “X {xn} = {x1, x2,…, xn-1}”), el algoritmo de fuerza bruta aplica la misma lógica de forma recursiva. Entonces, independientemente de qué rama tomamos, a continuación se considerará el valor xn-1 y, al principio, buscaremos una solución en la que xn-1 participe en el subconjunto de resultados, después de lo cual buscaremos una solución en la que no participe.
Mientras la recursividad se profundiza, si la suma objetivo restante se vuelve cero, significa que actualmente estamos en la rama adecuada y los números considerados ya se acumulan hasta la suma objetivo original 'q'.
El pseudocódigo del algoritmo de fuerza bruta mencionado queda así:
// Busca un subconjunto de 'X' que tenga una suma igual // a 'q' y lo coloca en 'Y'. Se supone que el conjunto 'X' // tiene 'n' números enteros. procedimiento ssp_brute_force( X[1..n]: conjunto de enteros, n: entero, q: entero, Y: referencia al conjunto de enteros) si q==0 entonces // Al seleccionar los enteros adecuados en 'Y', hemos // reducido iterativamente 'q' a cero, por lo que el subconjunto // de solución ya está en 'Y'. print Y return // No es necesario hacer nada más en esta rama si n==0 entonces // 'q' no es cero, mientras que el conjunto de entrada 'X' está // agotado. Esta rama no condujo a una solución. return // Pruebe con 'X[n]' en el subconjunto de soluciones, coloque X[n] en Y ssp_brute_force( X{X[n]}, n-1, qX[n], Y ) // Continúe buscando con el conjunto reducido // ('X' sin el último entero X[n]), // tal subconjunto, que suma 'qX[n]'. elimine X[n] de Y // Pruebe sin 'X[n]' ssp_brute_force( X{X[n]}, n-1, q, Y ) // Continúe buscando con el conjunto reducido // ('X' sin el último entero X[n]), // para tal subconjunto, que todavía suma 'q'.
En el pseudocódigo, vemos que resolver el problema para 'n' elementos de entrada requiere resolver dos problemas, cada uno con 'n-1' elementos de entrada. Cada uno de estos, a su vez, requerirá resolver dos problemas reducidos, esta vez con 'n-2' elementos de entrada, lo que dará como resultado en total 4 problemas con 'n-2' elementos de entrada cada uno. De esta manera, el número de problemas se duplica con cada llegada de un nuevo elemento de entrada, lo que hace que la complejidad temporal del algoritmo de fuerza bruta sea exponencial: O(2n).
En la práctica, este algoritmo sólo se puede utilizar si 'n' es suficientemente pequeño.
Sin embargo, los siguientes algoritmos para el problema de la suma del subconjunto que se describirán en este artículo todavía se basan en la lógica de "usar versus no usar" el elemento actual.
2. Suma de subconjuntos y problemas NP-completos
Existe una clase de problemas en Ciencias de la Computación, llamada “NP-completo”, que consiste en problemas que se consideran difíciles de resolver. El problema de suma de subconjuntos descrito pertenece a la clase NP-completa. Más precisamente, para que un problema sea NP-completo, se deben cumplir los siguientes criterios:
Es un problema de decisión, lo que significa que para cualquier entrada al problema, la salida es "sí" o "no". Con respecto al problema de la suma de subconjuntos, cualquier entrada que consista en un conjunto de valores de entrada X = {x1, x2,…, xn} y una suma objetivo 'q' da como resultado una respuesta de "sí" o "no": podemos elegir un subconjunto que se acumula hacia 'q', o no. Cuando la respuesta es “sí”, esto se puede demostrar mediante la existencia de una solución corta (de longitud polinómica). Con respecto al SSP, si es posible seleccionar y presentar dicho subconjunto Y⊆X, podemos sumar fácilmente todos sus números enteros y comprobar si realmente es igual a 'q' o no. La exactitud de cada solución se puede verificar rápidamente (es decir, en tiempo polinómico), y un algoritmo de búsqueda de fuerza bruta puede encontrar una solución probando todas las soluciones posibles. La solución de fuerza bruta para el problema de la suma de subconjuntos es la que acabamos de recordar en el capítulo anterior. El problema se puede utilizar para simular cualquier otro problema para el cual podamos verificar rápidamente que la solución es correcta. Por lo tanto, si pudiéramos encontrar rápidamente soluciones a algún problema NP-completo, podríamos encontrar rápidamente las soluciones de cualquier otro problema al que una solución dada pueda convertirse fácilmente.
La última afirmación muestra que también existen otros problemas NP-completos, así como que cualquiera de ellos puede convertirse en otro. Entonces, si se encuentra un algoritmo de tiempo polinomial para un problema NP completo, podríamos usarlo para resolver cualquier otro problema NP completo, convirtiéndolo al anterior. Aquí hay un diagrama de conversión común entre diferentes problemas NP-completos:
Vemos que, por ejemplo, el “problema de satisfacibilidad de la fórmula booleana” se puede convertir en el “problema de suma de subconjuntos”, mientras que este último se puede convertir en el “problema de mochila”.
3. La solución de programación dinámica del problema de la suma de subconjuntos
La solución común del problema de suma de subconjuntos (SSP) utiliza una técnica de programación dinámica. El principio de cualquier algoritmo de programación dinámica radica en resolver inicialmente problemas de tamaños más pequeños y luego utilizar esas soluciones para resolver el gran problema inicial.
Sea “S” una matriz booleana que tiene dimensiones “S[0..n][0..q]”, con
“S[i][p]” indica si podemos obtener la suma 'p' eligiendo solo entre los primeros elementos de entrada 'i'.
X = {8, 4, 11, 3, 9},
q = 28.
En el primer capítulo ya expresamos el valor “S[n][q]” de forma recursiva. “S[n][q]” indica si podemos obtener la suma 'q' eligiendo entre todos los 'n' enteros de entrada, que es la respuesta al problema inicial. Allí abordamos dos casos:
Si el último elemento 'xn' participa en el subconjunto de resultados 'Y', entonces deberíamos poder obtener la suma 'q–xn' eligiendo entre los primeros elementos de entrada 'n-1'. En otras palabras, "S[n-1][q–xn]" debería ser igual a "verdadero". De lo contrario, si el último elemento 'xn' no participa en el subconjunto de resultados 'Y', entonces deberíamos lograr obtener la suma objetivo 'q' eligiendo también entre los primeros elementos de entrada 'n-1'. En otras palabras, "S[n-1][q]" debería ser igual a "verdadero" entonces.
No existe una tercera opción. Si se cumple cualquiera de estas dos condiciones, entonces la suma objetivo 'q' es alcanzable. Si ambos se satisfacen, significa que 'q' se puede obtener seleccionando 'xn' y no incluyéndolo en el subconjunto de resultados 'Y'.
Entonces la fórmula del problema inicial queda:
[begin{ecuación*}
S[n][q] = S[n-1][q-x_n] o S[n-1][q]
end{ecuación*}]
Y funciona no sólo para “S[n][q]” sino también para cualquier “S[i][p]”, ya que la lógica sigue siendo la misma:
[begin{ecuación*}
S[i][p] = S[i-1][p-x_i] o S[i-1][p]
end{ecuación*}]
Ahora, al llenar la matriz “S[0..n][0..q]”, vemos que el valor de cualquier celda 'S[i][p]' depende únicamente de otras dos celdas, ambas situadas en la fila de arriba:
S[2][14]y S[2][3](los celestes).
Esto significa que podemos calcular la matriz en orden de arriba hacia abajo, lo que garantizará que en el momento en que se calcula “S[i][p]”, ya conocemos los valores de “S[i-1][p–xi]” y “S[i-1][p]”.
Las celdas amarillas aún no están calculadas.
Lo que se requiere para iniciar el cálculo es el contenido de la primera fila “S[0][p], p∈[0..q]”. La celda “S[0][p]” indica si es posible reunir la suma 'p', teniendo sólo los primeros 0 elementos de entrada (es decir, sin ningún elemento)”. Obviamente, la respuesta es “falso” si “p>0” y es “verdadera” sólo si “p==0” (podemos obtener la suma 0, sin utilizar ningún ítem).
Dicho esto, podemos calcular todas las celdas de la tabla en orden de arriba hacia abajo. Para nuestro conjunto de entrada, el resultado será:
eligiendo entre los 5 elementos de entrada.
El pseudocódigo de la solución de Programación Dinámica pasa a ser:
// Dado un conjunto de números enteros 'X' de n longitudes, devuelve si es posible // encontrar dicho subconjunto del mismo, que sume 'q'. función ssp_dynamic_programming( X[1..n]: conjunto de números enteros, n: número entero, q: número entero): booleano S[0..n][0..q]: matriz de valores booleanos // Llenar la primera fila de 'S' S[0][0]:= verdadero para p en [1..q] S[0][p] := false // Completa el contenido de la matriz para i en [1..n] para p en [0..q] si p < x[i] S[i][p] := S[i-1][p] else S[i][p] := S[i-1][px[i]] o S[i-1][p] // La respuesta está en la celda inferior derecha return S[n][q]
La celda inferior derecha “S[n][q]” contendrá la respuesta al problema original, indicando si podemos obtener la suma 'q' eligiendo entre todos los 'n' elementos de entrada.
La solución presentada requiere llenar la matriz “S”, que tiene celdas “(n+1)*(q+1)”. El cálculo de cada celda se realiza en tiempo O(1). Por tanto, la complejidad temporal del algoritmo de programación dinámica pasa a ser O(nq). Esta solución se llama pseudopolinomio porque aquí el factor 'q' no es proporcional a ningún polinomio del tamaño del problema. De hecho, 'q' puede ser proporcional incluso al exponente del tamaño del problema.
4. Presentación del algoritmo basado en intervalos
En el caso general, la tabla “S” completada en el capítulo anterior puede tener al final un contenido bastante impredecible. Sin embargo, si los valores de entrada “X = {x1, x2,…, xn}” satisfacen ciertas condiciones, las filas de la tabla llena pueden contener muchas celdas adyacentes con valores “verdaderos”, así como muchas celdas adyacentes con valores “falsos”.
X = {9, 4, 3, 12, 5},
q = 30.
En la fila actual, designemos las celdas adyacentes con un valor "verdadero" como "intervalos verdaderos" y las celdas adyacentes con un valor "falso" como "intervalos falsos".
Si sabemos de antemano que la tabla calculada “S” tendrá intervalos verdaderos suficientemente largos y/o intervalos falsos suficientemente largos al final, tendrá sentido calcular “S” no basado en celdas (como hicimos en el capítulo anterior), sino basado en intervalos.
Luego, en lugar de representar cada fila como una matriz booleana, la representaremos como una secuencia de intervalos verdaderos ordenados. Dentro de la fila actual, los intervalos verdaderos nunca se cruzan, por lo que podemos mantenerlos ordenados por sus puntos iniciales. Además, para simplificar las fórmulas que aparecerán más adelante, cuando denotamos un intervalo verdadero, nos referiremos a un rango medio abierto [a..b). Entonces, por ejemplo, un intervalo verdadero [5..8) significará que en la fila actual, las celdas 5, 6 y 7 son iguales a "verdadero", mientras que la celda 8 es "falso".
Ahora bien, teniendo los intervalos verdaderos (más adelante denominados simplemente “intervalos”, ya que los intervalos falsos no desempeñan un papel en el algoritmo que se describirá) de la fila anterior 'i-1', ¿cómo deberíamos calcular los intervalos de la fila actual 'i'? Recordemos la fórmula para llenar la tabla:
[begin{ecuación*}
S[i][p] = S[i-1][p-x_i] o S[i-1][p]
end{ecuación*}]
Si lo modifica por un momento y supone que solo existe la segunda parte de la expresión OR:
[begin{ecuación*}
S[i][p] = S[i-1][p]
end{ecuación*}]
dará como resultado que todas las celdas de la fila anterior se copien en la fila actual. En otras palabras, para eso bastaría con copiar los intervalos de la fila 'i-1' a la fila 'i'.
Por otro lado, si alteramos la fórmula de otra manera, suponiendo que solo existe la primera parte de la expresión OR:
[begin{ecuación*}
S[i][p] = S[i-1][p-x_i]
end{ecuación*}]
Aún así se copiarán todas las celdas de la fila anterior a la fila actual, pero esta vez desplazadas en las posiciones 'xi' hacia la derecha. Entonces eso es lo que habrá que hacer también con los intervalos:
Finalmente, refiriéndose a la fórmula original:
[begin{ecuación*}
S[i][p] = S[i-1][p-x_i] o S[i-1][p]
end{ecuación*}]
requiere que hagamos “O” en las dos secuencias de intervalos obtenidas, que es lo mismo que unirlas geométricamente.
Resumiendo lo dicho anteriormente, al llenar la tabla de intervalos verdaderos, para calcular el contenido de la fila 'i' debemos:
desplaza el contenido de la fila 'i-1' hacia la derecha en las posiciones 'xi' y únelo con el contenido original de la fila 'i-1'.
Tenga en cuenta que esto también significa que el intervalo de la fila 'i' (punto final derecho del intervalo más a la derecha) siempre será mayor en unidades 'xi' que el intervalo de la fila 'i-1'.
Entonces el intervalo de cualquier fila 'i' se puede calcular como:
[begin{ecuación*}
intervalo(i) = 1 + x_1 + x_2 + … + x_i = 1 + sum_{k=1}^i x_k
end{ecuación*}]
donde el término libre “1” viene debido a que todos los intervalos están medio abiertos (el intervalo inicial en la fila 0 es [0, 1), por lo que “span(0) = 1”).
Teniendo en cuenta que la fila anterior 'i-1' tiene intervalos 'c', desplazarlos todos en xi obviamente requerirá tiempo O(c). El cálculo de la unión de 2 secuencias, cada una con intervalos 'c', también se puede realizar en tiempo O(c) si se escanean ambas secuencias de izquierda a derecha.
simultáneamente. Esto significa que la transición de la fila anterior a la actual requiere un tiempo O(c).
Suponiendo que el número máximo de intervalos en cualquier fila es 'c', la complejidad temporal del algoritmo basado en intervalos pasa a ser O(nc).
La nota importante que debemos hacer aquí es que el valor 'c' depende significativamente del orden de los valores de entrada “X = {x1, x2,…, xn}”. Aquí hay un ejemplo con valores “n=5”, que al final produce muchos intervalos en la tabla.
X = {6, 11, 4, 2, 5}.
Y aquí está el problema resuelto con el mismo conjunto de valores de entrada “X={x1, x2,…, xn}”, pero ordenados en un orden diferente, más precisamente, en orden ascendente.
X = {2, 4, 5, 6, 11}.
Este comportamiento es bastante intuitivo: si queremos que los intervalos de la fila actual sean lo más pequeños posible, su extensión debería crecer lo más lentamente posible. Y una forma obvia de lograrlo es considerar todos los valores de entrada xi en orden ascendente.
5. Restaurar el subconjunto exacto de valores
La solución de programación dinámica del problema de la suma de subconjuntos, que revisamos en el capítulo 3, no solo responde si es posible obtener la suma 'q' dada a partir de los elementos de entrada “X = {x1, x2, …, xn}”, sino que también especifica el subconjunto exacto de 'X' (denotémoslo como 'Y', 'Y⊆X'), cuyos elementos suman 'q'. Para recuperar 'Y', debemos movernos sobre la mesa en la dirección opuesta: de abajo hacia arriba.
La última celda de la tabla “S[n][q]”, que contiene la respuesta al problema original, se calculó mediante la fórmula:
[begin{ecuación*}
S[n][q] = S[n-1][q-x_n] o S[n-1][q]
end{ecuación*}]
Si “S[n][q]” parece ser verdadero (lo que significa que la suma objetivo 'q' es alcanzable), significa que al menos uno de los 2 operandos de la expresión OR también es "verdadero". Así, podemos comprobar 2 casos:
Si “S[n-1][q] == verdadero”, significa que la suma objetivo 'q' también se puede obtener eligiendo solo entre los primeros elementos de entrada 'n-1'. Entonces, el último elemento 'xn' no participa en 'Y' y podemos continuar construyendo 'Y' solo a partir de los primeros elementos 'n-1'. Si "S[n-1][q–xn] == verdadero", significa que los primeros elementos de entrada 'n-1' participaron en la construcción de la suma 'q–xn', después de lo cual agregamos el último elemento 'xn' y obtuvimos la suma necesaria 'q'. Así que en realidad se utilizó el último elemento 'xn', y ahora debemos construir otra suma objetivo 'q–xn', eligiendo solo entre los primeros elementos de entrada 'n-1'.
Este juicio responde si el último elemento 'xn' participa en la suma objetivo 'q'. Pero la misma lógica también funciona para calcular la participación de cualquier otro elemento de entrada 'xi', en cualquier otra suma objetivo 'p'. Recordando la fórmula general mediante la cual se llenó toda la tabla:
[begin{ecuación*}
S[i][p] = S[i-1][p-x_i] o S[i-1][p]
end{ecuación*}]
Se puede hacer un juicio similar en el caso de que haya algún “S[i][p] == verdadero”, lo que nos ayudará a comprender si el elemento 'xi' participa en la formación de la suma 'p', o no.
Entonces, para reconstruir el subconjunto completo 'Y', simplemente aplicamos este principio repetidamente. El pseudocódigo para recuperar 'Y' se convierte en:
// Dada la matriz rellena 'S', devuelve un subconjunto exacto de // el conjunto de n longitudes 'X', cuyos enteros suman 'q'. función get_subset( X[1..n]: conjunto de enteros, n: entero, q: entero, S[0..n][0..q]: matriz de valores booleanos): conjunto de enteros si S[n][q] == false entonces devuelve ∅ // 'q' no se puede obtener Y := conjunto vacío de enteros mientras n > 0 // Aquí sabemos que “S[n][q]” siempre es verdadero si S[n-1][q] == verdadero entonces // El elemento 'x[n]' no se puede usar en 'Y' else // El elemento 'x[n]' debe usarse en 'Y' inserta X[n] en Y q := qX[n] // Queda para construir la suma 'qX[n]' // Moverse hacia arriba al elemento anterior n := n-1 devuelve Y
La complejidad temporal de esta función es O(n), ya que en cada iteración nos movemos hacia arriba una fila sobre la tabla, mientras que su altura es 'n+1'.
En nuestro ejemplo, la reconstrucción del subconjunto de resultados 'Y' se realiza mediante la siguiente ruta:
X = {9, 4, 3, 12, 5},
q = 30.
Paso 1: Aquí tenemos 'S[n][q] = S[5][30]= verdadero' (círculo verde más a la derecha), lo que significa que la suma objetivo 'q=30' es alcanzable. Vemos que es[4][30]= falso' (círculo azul arriba), por lo que la suma '30' no se puede obtener si se elige entre los primeros 4 elementos. Entonces, necesitamos el elemento 'x5=5' para la construcción.
Paso 2: Queda por construir la suma '30-5=25', eligiendo entre los primeros 4 elementos (segundo círculo verde). Vemos que es[3][25]= falso' (círculo azul), lo que significa que '25' no se puede construir si se elige solo entre los primeros 3 elementos. Entonces necesitamos usar el elemento 'x4=12'.
Paso 3: Resta construir la suma '25-12=13', eligiendo entre los 3 primeros elementos (3er círculo verde). Vemos que es[2][13]= verdadero' (cuarto círculo verde), lo que significa que '13' también se puede obtener eligiendo solo entre los 2 primeros elementos. Por eso omitimos el elemento 'x3=3'.
Paso 4: Ahora debemos construir la suma '13', eligiendo entre los 2 primeros elementos. Vemos que es[1][13]= falso' (círculo azul), lo que significa que no podemos obtener la suma '13' si usamos solo el primer elemento 'x1'. Entonces necesitamos usar 'x2=4' para eso.
Paso 5: Queda por construir la suma '13-4=9', eligiendo solo el primer elemento de entrada (quinto círculo verde). Así que lo tomamos como 'x1=9'.
¿Podemos actuar de manera similar en la solución basada en intervalos? Vemos que lo único que se necesita para reconstruir el subconjunto 'Y' en la solución de programación dinámica es conocer el valor de la celda “S[i][p]”, que, en relación con la solución basada en intervalos, es saber si la i-ésima secuencia de intervalos cubre la coordenada 'p'. Esto se puede verificar ejecutando una búsqueda binaria en la i-ésima secuencia de intervalos ordenada actual.
Suponiendo que la secuencia i-ésima contiene intervalos 'ci', la búsqueda binaria tomará tiempo O (log ci). Para recuperar el subconjunto completo 'Y', ejecutamos una búsqueda binaria en cada una de las 'n' secuencias de intervalos. Si hay como máximo intervalos 'c' en cada fila, la recuperación del subconjunto de resultados 'Y' se ejecutará en un tiempo O(n log c). Probablemente se puedan aplicar técnicas como la cascada fraccional aquí para acelerar el proceso de recuperación del subconjunto.
6. Complejidad temporal del algoritmo basado en intervalos
En el Capítulo 4, derivamos la complejidad temporal del algoritmo basado en intervalos como O(nc), donde 'n' es el número de valores de entrada y 'c' es el número máximo de intervalos en una fila. También observamos allí que el orden de los valores de entrada “X = {x1, x2,…, xn}” es importante y que 'c' generalmente da como resultado un valor más pequeño cuando los elementos de 'X' llegan en orden creciente. Ahora bien, ¿existen casos de entrada para los cuales el valor 'c' será realmente pequeño?
Caso 1: una progresión geométrica
Primero consideremos el caso en el que los valores de 'X' forman una progresión geométrica con un valor inicial de '1' y una proporción común de '2':
[begin{ecuación*}
X = { 1, 2, 4, 8, 16,…, 2^{n-1} } : x_i = 2^{i-1}
end{ecuación*}]
¿Qué forma tendrá el conjunto de intervalos construidos?
Como ya sabemos, teniendo intervalos de la fila anterior 'i-1', para calcular intervalos de la fila actual 'i', hay 2 pasos:
compensar todos los intervalos de la fila 'i-1' por 'xi' a la derecha, unir los desplazamientos con el contenido original de la fila 'i-1'.
Hacer eso en la entrada mencionada dará como resultado:
la fila 0 siempre tiene solo un intervalo [0, 1), lo que indica que solo se puede lograr la suma '0' si no se utiliza ningún elemento de entrada. como 'x1=1', el intervalo desplazado pasa a ser “[0,1) >> 1 = [1,2)”, y luego de unir con el original tenemos: “[0,1) ꓴ [1,2) = [0,2)”, como 'x2=2', el intervalo desplazado pasa a ser “[0,2) >> 2 = [2,4)”, y luego de unir con el original tenemos: “[0,2) ꓴ [2,4) = [0,4)”, como 'x3=4', el intervalo desplazado pasa a ser “[0,4) >> 4 = [4,8)”, y luego de unir con el original tenemos: “[0,4) ꓴ [4,8) = [0,8)”, y así sucesivamente…
Vemos que cada fila 'i' tiene solo 1 intervalo: [0,2i).
X = {1, 2, 4, 8, 16,…}
Por supuesto, el caso presentado es muy especial, y no sorprende que cualquier suma objetivo 'q ∈ [0, 2n)' pueda construirse a partir de esos 'n' números. Si representa 'q' en el sistema posicional numérico binario, entonces sus dígitos '1' corresponderán a las potencias de '2' (los valores de entrada), que deben sumarse para obtener 'q'.
Caso 2: Más lento que una progresión geométrica
Los valores crecen rápidamente en cualquier progresión geométrica. En el caso anterior, como la razón común era igual a 2, también podríamos expresar cada valor 'xi' como la suma de todos los valores anteriores más 1:
[begin{ecuación*}
x_i = 1 + sum_{k=1}^{i-1} x_k
end{ecuación*}]
¿Qué pasa si la secuencia 'X' crece más lentamente? En otras palabras, ¿qué pasa si después de ordenar todos los valores de 'X' en orden creciente, cada valor 'xi' resulta menor o igual a la suma de todos los valores anteriores, más 1?
[begin{ecuación*}
hspace{1cm} x_i leq 1 + sum_{k=1}^{i-1} x_k hspace{1cm} (1)
end{ecuación*}]
Para entender cómo se derivarán los intervalos en tal caso, recordemos del Capítulo 4 que el intervalo de la fila 'i' es igual a la suma de todos los valores de entrada anteriores y actuales, más 1:
[begin{ecuación*}
intervalo(i) = 1 + sum_{k=1}^{i} x_k
end{ecuación*}]
Ahora, si cada valor 'xi' es menor o igual a la suma de todos los valores anteriores, significa que 'xi' también es menor que el intervalo de su fila anterior:
[begin{ecuación*}
x_i leq 1 + sum_{k=1}^{i-1} x_k = intervalo(i-1)
end{ecuación*}]
lo que significa que si solo hay un intervalo en la fila 'i-1', unirlo con su desplazamiento hacia la derecha por 'xi' dará como resultado solo un intervalo en la fila 'i'. Inicialmente, tenemos sólo un intervalo en la fila 'i=0'. Entonces, en el caso de que los valores de entrada crezcan más lentamente que la progresión geométrica mencionada (1), cada fila de la tabla tendrá solo un intervalo.
X = {1, 2, 3, 6, 11, 20},
Concluyendo este caso, si después de ordenar todos los valores de entrada de 'X' cada vez más, tenemos la restricción:
[begin{ecuación*}
x_i leq 1 + sum_{k=1}^{i-1} x_k
end{ecuación*}]
la tabla tendrá solo un intervalo “c=1” en cada fila, y el algoritmo basado en intervalos se ejecutará en un tiempo O(n) garantizado. Observemos que desde la perspectiva práctica, tal restricción a menudo podría satisfacerse. Si los datos de entrada vienen en orden aleatorio, se necesitará un tiempo O (n log n) adicional para ordenarlos.
Caso 3: Casi más lento que una progresión geométrica
Generalicemos el caso anterior 2, que tenía la restricción:
[begin{ecuación*}
x_i leq 1 + sum_{k=1}^{i-1} x_k
end{ecuación*}]
Ahora permitiremos que se viole de vez en cuando.
Una vez que eso suceda para algunos 'xi', podemos esperar que el número de intervalos 'c' en la fila 'i' aumente. Pero ¿cuánto tiempo puede crecer 'c'? Observémoslo en el siguiente ejemplo:
norte = 7,
X = {1, 2, 5, 7, 10, 28, 30},
Nos resultará más fácil escribir otra matriz 'XP', donde 'xpi' es igual a la suma de todos los valores anteriores:
XP = {0, 1, 3, 8, 15, 25, 53, 83}
… vemos que la condición mencionada se viola en los valores de entrada 'x3=5' (como 'x3>xp3+1') y 'x6=28' (como 'x6>xp6+1').
Ahora construyamos los intervalos. Esta vez, como el span de todas las entradas es grande (“span(n) = 83+1 = 84”), para las 2 últimas filas escribiremos las secuencias de intervalos, en lugar de presentarlas geométricamente:
Como podemos ver, si para algún 'xi' se viola la condición mencionada, el número de intervalos se duplica en esa fila. En nuestro ejemplo, esto ocurrió para los valores de entrada 'x3' y 'x6'. Sucede porque todos los intervalos desplazados aparecen hacia la derecha desde el intervalo de los intervalos actuales:
Sin embargo, en las otras filas, el número de intervalos tiende a no aumentar mucho, porque muchos de ellos, después de unirse con el contenido de la fila actual, simplemente se convierten en un intervalo largo. En nuestro ejemplo, eso sucedió explícitamente en la última fila 'x7=30'.
El nombre de este artículo proviene del hecho de que si todos los elementos de entrada “X = {x1, x2,…, xn}” están lo suficientemente cerca entre sí, muchos intervalos tenderán a unirse durante la construcción de arriba hacia abajo de la tabla, por lo que la constante 'c' podría permanecer acotada con cierta probabilidad. Si ese es el caso, terminaremos con una solución de tiempo lineal “O(nc) = O(n)” para el problema de la suma de subconjuntos, suponiendo que los valores de entrada lleguen ordenados. De lo contrario, la clasificación inicial de los valores de 'X' se convierte en el paso que consume más tiempo y requiere tiempo adicional “O(n log n)”.
Caso 4: Más rápido que una progresión geométrica
Consideremos un caso más, cuando los valores de entrada ordenados
“X = {x1, x2, …, xn}” crece más rápido que la progresión geométrica mencionada con una proporción común de 2. Eso sucederá si cada valor 'xi' es mayor que la suma de todos los valores anteriores, más 1:
[begin{ecuación*}
hspace{1cm} x_i > 1 + sum_{k=1}^{i-1} x_k hspace{1cm} (2)
end{ecuación*}]
En el caso anterior 3, ya notamos que una vez que sucede para algún 'xi' (es decir, cuando 'xi' aparece hacia la derecha del intervalo de todos los valores anteriores), el número de intervalos se duplica, porque no quedan fragmentos comunes entre las secuencias de intervalos actuales y desplazadas.
Y en el caso actual, cuando 'X' crece más rápido que una progresión geométrica con una proporción común de 2, sucede para cada valor de entrada 'xi', por lo que el número de intervalos se duplica en cada fila, lo que resulta en un crecimiento exponencial.
Consideremos el siguiente ejemplo:
norte = 6,
X = {2, 5, 9, 20, 39}.
La matriz con sumas de todos los valores anteriores será:
XP = {0, 2, 7, 16, 36, 75}.
Entonces vemos que cada elemento 'xi' es mayor que la suma de todos los elementos anteriores, más 1. La construcción de intervalos dará como resultado la siguiente tabla:
Entonces vemos que si los valores de entrada "X" tienen la restricción mencionada (2), continuar con el algoritmo basado en intervalos no es la mejor idea, ya que dará como resultado 2n intervalos cortos en la última fila, por lo que requerirá O(2n) tiempo para ejecutarse. Si sabemos de antemano que este será nuestro caso, se puede aplicar otro algoritmo basado en decisiones, que seleccionará un subconjunto necesario de "X" en el tiempo lineal O(n).
Conclusión
En este artículo, hemos observado un enfoque novedoso para resolver el problema de la suma de subconjuntos, llamado "algoritmo basado en intervalos". Es similar a la solución de Programación Dinámica, con la diferencia de que aquí no operamos en celdas individuales de la tabla, sino en sus rangos continuos.
Hemos observado 4 distribuciones especiales de valores de entrada y hemos demostrado que si las entradas son lo suficientemente densas, el algoritmo basado en intervalos se ejecuta en tiempo lineal. También hemos demostrado que cuando las entradas son "casi densas", el algoritmo aún podría funcionar lo suficientemente rápido. Similar a la solución de programación dinámica, el algoritmo basado en intervalos permite obtener el subconjunto exacto, cuyos elementos suman el objetivo dado.
El problema de la suma de subconjuntos es uno de los problemas NP-completos; por lo tanto, este artículo destaca otro caso especial de entradas, para las cuales se pueden resolver con la suficiente rapidez.
Me alegra que hayas leído hasta el final y ¡gracias por tu interés!
Todas las ilustraciones utilizadas están preparadas por Lilit Danielyan (https://www.behance.net/lilitdanielyan1).
Si disfrutó leyendo, no dude en conectarse conmigo en LinkedIn y enviarme un mensaje privado para compartir sus pensamientos. ¡Sin duda me gustaría! (https://www.linkedin.com/in/tigran-hayrapetyan-cs/).
Todas las imágenes utilizadas, a menos que se indique lo contrario, están diseñadas a petición del autor.