TL;DR
En este artículo, trato de explicar las diferencias/similitudes entre la programación dinámica y los enfoques de divide y vencerás basándome en dos ejemplos: búsqueda binaria y distancia mínima de edición (distancia de Levenshtein).
El problema
Cuando comencé a aprender algoritmos, me resultó difícil comprender la idea principal de la programación dinámica (DP) y en qué se diferencia del enfoque divide y vencerás (DC). Cuando se trata de comparar esos dos paradigmas, generalmente la función de Fibonacci viene al rescate como un gran ejemplo.. Pero cuando estamos tratando de resolver el mismo problema utilizando los enfoques DP y DC para explicar cada uno de ellos, me parece que podemos perder detalles valiosos que podrían ayudar a detectar la diferencia más rápido. Y estos detalles nos dicen que cada técnica sirve mejor para diferentes tipos de problemas.
Todavía estoy en el proceso de comprender la diferencia de DP y DC y no puedo decir que haya captado completamente los conceptos hasta ahora. Pero espero que este artículo arroje algo de luz adicional y lo ayude a dar otro paso en el aprendizaje de paradigmas de algoritmos tan valiosos como la programación dinámica y divide y vencerás.
Similitudes entre la programación dinámica y el divide y vencerás
Como lo veo por ahora, puedo decir que la programación dinámica es una extensión del paradigma divide y vencerás.
No los trataría como algo completamente diferente. Porque ambos funcionan descomponiendo recursivamente un problema en dos o más subproblemas del mismo tipo o relacionados, hasta que se vuelven lo suficientemente simples como para resolverlos directamente. Las soluciones a los subproblemas luego se combinan para dar una solución al problema original.
Entonces, ¿por qué todavía tenemos diferentes nombres de paradigmas entonces y por qué llamé a la programación dinámica una extensión? Esto se debe a que el enfoque de programación dinámica se puede aplicar al problema solo si el problema tiene ciertas restricciones o requisitos previos. Y después de eso, la programación dinámica extiende el enfoque divide y vencerás con la técnica de memorización o tabulación.
Vayamos paso a paso…
Prerrequisitos/Restricciones de Programación Dinámica
Como acabamos de descubrir, hay dos atributos clave que debe tener el problema de divide y vencerás para que la programación dinámica sea aplicable:
Una vez que se cumplen estas dos condiciones, podemos decir que este problema de divide y vencerás se puede resolver utilizando el enfoque de programación dinámica.
Extensión de programación dinámica para divide y vencerás El
enfoque de programación dinámica amplía el enfoque de divide y vencerás con dos técnicas (memoización y tabulación) que tienen el propósito de almacenar y reutilizar soluciones de subproblemas que pueden mejorar drásticamente el rendimiento. Por ejemplo, la implementación recursiva ingenua de la función de Fibonacci tiene una complejidad de tiempo de O (2 ^ n) donde la solución DP hace lo mismo con solo O (n) tiempo.
La memorización (llenado de caché de arriba hacia abajo) se refiere a la técnica de almacenamiento en caché y reutilización de resultados calculados previamente. La función fib memorizada se vería así:
memFib(n) {
if (mem[n] is undefined)
if (n < 2) result = n
else result = memFib(n-2) + memFib(n-1)
mem[n] = result
return mem[n]
}
La tabulación (llenado de caché de abajo hacia arriba) es similar pero se enfoca en llenar las entradas del caché. Calcular los valores en el caché es más fácil de hacer de forma iterativa. La versión de tabulación de fib se vería así:
tabFib(n) {
mem[0] = 0
mem[1] = 1
for i = 2...n
mem[i] = mem[i-2] + mem[i-1]
return mem[n]
}
Puede leer más sobre comparación de tabulación y memorización aquí .
La idea principal que debe comprender aquí es que debido a que nuestro problema divide y vencerás tiene subproblemas superpuestos, el almacenamiento en caché de las soluciones de los subproblemas se vuelve posible y, por lo tanto, la memorización/tabulación entra en escena.
Entonces, ¿cuál es la diferencia entre DP y DC después de todo?
Ya que ahora estamos familiarizados con los requisitos previos de DP y sus metodologías, estamos listos para poner todo lo mencionado anteriormente en una sola imagen.
Programación dinámica y dependencia de los paradigmas divide y vencerás
Vayamos y tratemos de resolver algunos problemas usando los enfoques DP y DC para que esta ilustración sea más clara.
Ejemplo de divide y vencerás: búsqueda binaria El algoritmo de búsqueda
binaria , también conocido como búsqueda de medio intervalo, es un algoritmo de búsqueda que encuentra la posición de un valor objetivo dentro de una array ordenada. La búsqueda binaria compara el valor objetivo con el elemento central de la array; si son desiguales, se elimina la mitad en la que no puede estar el objetivo y se continúa la búsqueda en la mitad restante hasta encontrar el valor del objetivo. Si la búsqueda termina con la mitad restante vacía, el objetivo no está en la array.
Ejemplo
Aquí hay una visualización del algoritmo de búsqueda binaria donde 4 es el valor objetivo.
Lógica de algoritmo de búsqueda binaria
Dibujemos la misma lógica pero en forma de árbol de decisión.
Árbol de decisión del algoritmo de búsqueda binaria
Puede ver claramente aquí un principio de divide y vencerás para resolver el problema. Estamos iterativamente dividiendo la array original en sub-arrays e intentando encontrar el elemento requerido allí.
¿Podemos aplicarle programación dinámica? No. Es porque no hay subproblemas superpuestos. Cada vez que dividimos la array en partes completamente independientes. Y de acuerdo con los requisitos previos/restricciones de divide y vencerás, los subproblemas deben superponerse de alguna manera.
Normalmente, cada vez que dibuja un árbol de decisión y en realidad es un árbol (y no un gráfico de decisión), significaría que no tiene subproblemas superpuestos y este no es un problema de programación dinámica.
El código
Aquí puede encontrar el código fuente completo de la función de búsqueda binaria con casos de prueba y explicaciones.
function binarySearch(sortedArray, seekElement) {
let startIndex = 0;
let endIndex = sortedArray.length - 1;
while (startIndex <= endIndex) {
const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
// If we've found the element just return its position.
if (sortedArray[middleIndex] === seekElement)) {
return middleIndex;
}
// Decide which half to choose: left or right one.
if (sortedArray[middleIndex] < seekElement)) {
// Go to the right half of the array.
startIndex = middleIndex + 1;
} else {
// Go to the left half of the array.
endIndex = middleIndex - 1;
}
}
return -1;
}
Ejemplo de programación dinámica: distancia mínima de edición
Normalmente, cuando se trata de ejemplos de programación dinámica, el algoritmo del número de Fibonacci se toma de forma predeterminada. Pero tomemos un algoritmo un poco más complejo para tener algún tipo de variedad que nos ayude a comprender el concepto.
La distancia de edición mínima (o distancia de Levenshtein) es una métrica de string para medir la diferencia entre dos secuencias. De manera informal, la distancia de Levenshtein entre dos palabras es el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por otra.
Ejemplo
Por ejemplo, la distancia de Levenshtein entre «gatito» y «sentado» es 3, ya que las siguientes tres ediciones cambian una a otra, y no hay forma de hacerlo con menos de tres ediciones:
Aplicaciones
Tiene una amplia gama de aplicaciones, por ejemplo, correctores ortográficos, sistemas de corrección para el reconocimiento óptico de caracteres, búsqueda de strings difusas y software para ayudar a la traducción del lenguaje natural basada en la memoria de traducción.
Definición matemática
Matemáticamente, la distancia de Levenshtein entre dos strings a, b (de longitud |a| y |b| respectivamente) viene dada por la función lev(|a|, |b|) donde
Nótese que el primer elemento en el mínimo corresponde a la eliminación (de a a b), el segundo a la inserción y el tercero a la coincidencia o no coincidencia, dependiendo de si los símbolos respectivos son los mismos.
Explicación
Bien, tratemos de averiguar de qué está hablando esa fórmula. Tomemos un ejemplo simple de encontrar la distancia de edición mínima entre las strings ME y MY. Intuitivamente, ya sabe que la distancia de edición mínima aquí es 1 operación y esta operación es «reemplazar E con Y». Pero intentemos formalizarlo en forma de algoritmo para poder hacer ejemplos más complejos como transformar el sábado en domingo.
Para aplicar la fórmula a la transformación ME>MY, necesitamos conocer las distancias de edición mínimas de las transformaciones ME>M, M>MY y M>M anteriores. Luego necesitaremos elegir el mínimo y agregar la operación +1 para transformar las últimas letras E?Y.
Entonces, ya podemos ver aquí una naturaleza recursiva de la solución: la distancia de edición mínima de la transformación ME>MY se calcula en función de tres transformaciones posibles previamente. Por lo tanto, podemos decir que este es un algoritmo de divide y vencerás.
Para explicar esto mejor, dibujemos la siguiente array.
Ejemplo simple de encontrar la distancia de edición mínima entre ME y MY strings
La celda (0, 1) contiene el número rojo 1. Significa que necesitamos 1 operación para transformar M en una string vacía: eliminar M. Es por eso que este número es rojo.
La celda (0, 2) contiene el número rojo 2. Significa que necesitamos 2 operaciones para transformar ME en una string vacía: eliminar E, eliminar M. La
celda (1, 0) contiene el número verde 1. Significa que necesitamos 1 operación para transforme una string vacía en M: inserte M. Es por eso que este número es verde.
La celda (2, 0) contiene el número verde 2. Significa que necesitamos 2 operaciones para transformar la string vacía en MI: inserte Y, inserte M.
La celda (1, 1) contiene el número 0. Significa que no cuesta nada transformar M a M.
La celda (1, 2) contiene el número rojo 1. Significa que necesitamos 1 operación para transformar ME a M: eliminar E.
Y así sucesivamente…
Esto parece fácil para una array tan pequeña como la nuestra (solo es 3×3). Pero, ¿cómo podríamos calcular todos esos números para arrays más grandes (digamos una de 9×7, para la transformación sábado>domingo)?
La buena noticia es que, según la fórmula, solo necesita tres celdas adyacentes (i-1, j), (i-1, j-1) e (i, j-1) para calcular el número de la celda actual (i , j) . Todo lo que tenemos que hacer es encontrar el mínimo de esas tres celdas y luego agregar +1 en caso de que tengamos letras diferentes en la fila y en la columna.
Entonces, una vez más, puede ver claramente la naturaleza recursiva del problema.
Naturaleza recursiva del problema de la distancia mínima de edición
Ok, acabamos de descubrir que estamos lidiando con el problema de divide y vencerás aquí. Pero, ¿podemos aplicarle un enfoque de programación dinámica? ¿Este problema satisface nuestros subproblemas superpuestos y las restricciones de subestructura óptima? Sí. Veámoslo desde el gráfico de decisión.
Gráfico de decisión para la distancia de edición mínima con subproblemas superpuestos
En primer lugar, esto no es un árbol de decisiones. Es un gráfico de decisión. Es posible que vea una serie de subproblemas superpuestos en la imagen que están marcados en rojo. Además, no hay forma de reducir el número de operaciones y hacerlo menor que un mínimo de esas tres celdas adyacentes de la fórmula.
También puede notar que cada número de celda en la array se calcula en función de los anteriores. Por lo tanto, aquí se aplica la técnica de tabulación (llenar el caché de abajo hacia arriba). Lo verás en el ejemplo de código a continuación.
Aplicando más estos principios podemos resolver casos más complicados como con la transformación sábado > domingo.
Distancia mínima de edición para convertir de sábado a domingo
El código
Aquí puede encontrar el código fuente completo de la función de distancia de edición mínima con casos de prueba y explicaciones.
function levenshteinDistance(a, b) {
const distanceMatrix = Array(b.length + 1)
.fill(null)
.map(
() => Array(a.length + 1).fill(null)
);
for (let i = 0; i <= a.length; i += 1) {
distanceMatrix[0][i] = i;
}
for (let j = 0; j <= b.length; j += 1) {
distanceMatrix[j][0] = j;
}
for (let j = 1; j <= b.length; j += 1) {
for (let i = 1; i <= a.length; i += 1) {
const indicator = a[i - 1] === b[j - 1] ? 0 : 1;
distanceMatrix[j][i] = Math.min(
distanceMatrix[j][i - 1] + 1, // deletion
distanceMatrix[j - 1][i] + 1, // insertion
distanceMatrix[j - 1][i - 1] + indicator, // substitution
);
}
}
return distanceMatrix[b.length][a.length];
}
Conclusión
En este artículo hemos comparado dos enfoques algorítmicos como la programación dinámica y divide y vencerás. Descubrimos que la programación dinámica se basa en el principio de divide y vencerás y solo se puede aplicar si el problema tiene subproblemas superpuestos y una subestructura óptima (como en el caso de la distancia de Levenshtein). Entonces, la programación dinámica utiliza la técnica de memorización o tabulación para almacenar soluciones de subproblemas superpuestos para su uso posterior.
¡Espero que este artículo no te haya causado más confusión, sino que haya arrojado algo de luz sobre estos dos importantes conceptos algorítmicos! 🙂
Puede encontrar más ejemplos de divide y vencerás y problemas de programación dinámica con explicaciones, comentarios y casos de prueba en el repositorio de estructuras de datos y algoritmos de JavaScript .
¡Feliz codificación!