La programación dinámica no es magia negra

 (qsantos.fr)
2 puntos por GN⁺ 2024-01-15 | 1 comentarios | Compartir por WhatsApp
  • Incluso problemas con muchos casos especiales, como Advent of Code 2023 Day 12, pueden abordarse con programación dinámica si encuentras una estructura donde se repiten los mismos subproblemas
  • La clave es dividir el problema con recursión, reducir cálculos duplicados con memoización y luego pasarlo a un cálculo iterativo que llena los valores necesarios en orden de dependencia
  • El ejemplo de Fibonacci muestra que la recursión ingenua evalúa f(1) repetidamente, pero con caché solo hace falta evaluar n + 1 valores desde f(0) hasta f(n)
  • La distancia de Levenshtein y Advent of Code Day 12 muestran cómo usar índices de estado como la longitud de la cadena o el índice de reglas como clave de caché para convertir llamadas recursivas en el llenado de un arreglo
  • Aprender programación dinámica no solo mejora el rendimiento, también deja ver los estados intermedios y las dependencias del algoritmo, y facilita encontrar oportunidades de optimización de memoria

El nombre confunde, pero la idea es simple

  • El nombre “dynamic programming” no está relacionado directamente con significados modernos como “estilo de programación” o “tipado dinámico”.
  • La idea central es dividir un problema en problemas más pequeños y parecidos, y reutilizar sus resultados.
  • Se añade una nota editorial que explica que la expresión sí tiene sentido si se toma “programming” en su significado histórico.
  • El punto de partida suele ser una forma de descomponer el problema en subproblemas, como una función recursiva.
  • Cuando el mismo subproblema aparece varias veces, surge de forma natural la necesidad de guardar el resultado y reutilizarlo mediante caché.

Caché e iteración con Fibonacci

  • La función de Fibonacci se define como f(n) = f(n - 1) + f(n - 2), y una implementación recursiva ingenua vuelve a calcular los mismos valores una y otra vez.
  • f(1) es un valor que realmente se suma al resultado final, así que a medida que f(n) crece, la cantidad de evaluaciones en la versión ingenua también aumenta rápidamente.
  • Si guardas resultados en caché o aplicas memoización, ya no hace falta recalcular f(4), f(3) o f(2).
  • Con este enfoque, solo se evalúan 7 valores desde f(0) hasta f(6); en general, se reduce a n + 1 evaluaciones.
  • Si avanzas un paso más y llenas los valores necesarios en orden a partir de f(0) y f(1), desaparecen las llamadas recursivas.
    • F[2] = F[1] + F[0]
    • F[3] = F[2] + F[1]
    • De la misma manera se calcula hasta F[6] = 8
  • En Fibonacci ni siquiera hace falta conservar todo el arreglo: basta con mantener el valor anterior y el previo a ese.
  • Este flujo muestra una ruta sistemática que va desde la definición matemática hasta una implementación iterativa.

Extender la idea al ejemplo de distancia de edición

  • La distancia de edición entre dos cadenas es la cantidad mínima de ediciones necesarias para transformar una cadena en otra.
  • El problema cambia según qué tipos de edición se permitan.
    • Si solo se permite sustitución de caracteres, es Hamming distance
    • Si también se permiten inserciones y eliminaciones, es Levenshtein distance
  • La distancia de Levenshtein puede dividirse en problemas más pequeños tomando como base el último carácter de las cadenas A y B.
    • Si el último carácter es igual, se ignoran ambos caracteres y se usa la distancia del resto de la cadena
    • Si el último carácter es distinto, se elige el costo mínimo entre sustitución, eliminación e inserción
    • Si A está vacía, hay que insertar todos los caracteres de B, así que el costo es b
    • Si B está vacía, hay que eliminar todos los caracteres de A, así que el costo es a
  • Si llevas esta definición tal cual a una recursión en Python, se vuelve muy lenta con cadenas largas y con muchas diferencias.
  • Si Fibonacci crecía aproximadamente en dos ramas por nivel del árbol de llamadas, esta recursión puede crecer en tres ramas según el caso.
  • Si agregas functools.cache en Python, puedes reutilizar los resultados de las mismas combinaciones de subcadenas.
  • Una implementación mejor evita crear nuevas cadenas todo el tiempo y solo pasa las cadenas originales A, B y las longitudes parciales a, b.
  • En la etapa final, se crea directamente un arreglo bidimensional cache, y se llena en orden para que cache[a][b] = levenstein(A[:a], B[:b]).
  • La versión iterativa recorre a y b desde 0 hasta la longitud de las cadenas, usando los valores ya llenados de la fila y la columna anteriores.

Aplicación a Advent of Code 2023 Day 12

  • El problema del 12 de diciembre de 2023 de Advent of Code consiste en resolver un nonogram unidimensional.
  • Una entrada de ejemplo tiene la forma .??..??...?##. 1,1,3, donde ? puede ser . o #.
  • Un enfoque de fuerza bruta usa backtracking, pero si hay n signos de interrogación, hay que evaluar 2^n candidatos, así que el crecimiento es exponencial.
  • Aparece una estructura donde se repiten los mismos subproblemas.
    • ..#..??...?##. (1),1,3
    • .#...??...?##. (1),1,3
    • Si descartas la parte inicial ya procesada, quedan problemas casi idénticos como .??...?##. 1,3 y ..??...?##. 1,3
  • La función básica de backtracking recibe conditions y rules y calcula cuántas disposiciones son posibles.
    • Si ya no quedan reglas, revisa si en las condiciones restantes hay #
    • Si ya no quedan condiciones, revisa si todavía quedan reglas
    • Si el carácter actual es . o ?, avanza una posición y sigue calculando
    • Si el carácter actual es # o ?, verifica el tamaño de la siguiente regla y la condición del separador, y luego pasa al siguiente estado
  • En Python, basta con agregar @cache para aplicar memoización.
  • Para convertirlo en programación dinámica, en lugar de ir cortando la cadena y las reglas, se usan como estado el desplazamiento i en la cadena y el desplazamiento j en las reglas.
  • Después se construye cache[i][j] directamente y se reemplaza la recursión por cálculo iterativo, llenando los índices en orden inverso.
  • El ejemplo de implementación en Rust se ofrece en el enlace Rust implementation dentro del artículo.

Lo que se ve al llenar la caché manualmente

  • La versión con programación dinámica de Advent of Code Day 12 puede parecer más lenta que la versión con memoización.
  • Esa diferencia podría deberse a una implementación de Python no optimizada.
  • Cuando construyes la caché manualmente, se ve mejor qué valores hacen falta de verdad.
  • En el problema Day 12, la versión de programación dinámica deja ver que solo hace falta la columna anterior.
  • Por eso, el arreglo bidimensional puede reemplazarse por dos arreglos unidimensionales que representen la columna anterior y la actual.

Problemas para practicar y conclusión

  • La programación dinámica no es trivial, pero tampoco es una técnica inaccesible para la mayoría de programadores.
  • Si entiendes cómo dividir un problema en problemas pequeños, en muchas situaciones la memoización por sí sola ya puede mejorar mucho una implementación ingenua.
  • Con más práctica, puedes entender mejor toda una familia de algoritmos, evaluar mejor los trade-offs y encontrar optimizaciones adicionales.
  • Se proponen los siguientes problemas para practicar.
  • Después de implementar, no hay que olvidar el benchmarking y profiling

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-01-15
Opiniones de Hacker News

  • Me gustó que el artículo señale que un algoritmo de programación dinámica no es más que una forma ingeniosa de cachear recursión. En mi experiencia, encontrar primero una solución recursiva es el mejor punto de partida para hallar una solución de programación dinámica y, una vez que la tienes, la memoización es fácil y puede dar una gran mejora de velocidad
    A veces incluso es más rápida que la programación dinámica ascendente, porque solo calcula las soluciones que realmente se necesitan. La clave es que está bien que haya muchos subproblemas en el árbol de llamadas, pero la cantidad de subproblemas distintos debe ser relativamente pequeña. No tiene sentido cachear un resultado que solo se necesita una vez, y la dificultad está en dividir el problema original en una cantidad suficientemente pequeña de subproblemas distintos

    • La parte de que debe haber relativamente pocos subproblemas distintos es clave. Que el algoritmo completo sea recursivo o iterativo es secundario, y la programación dinámica suele aparecer con frecuencia en algoritmos recursivos
    • La explicación de que “la programación dinámica es una forma de cachear recursión” fue lo que hizo que por fin me cayera el veinte. En la universidad, quizá porque en ese momento dominaba la programación procedural, los ejemplos de llenado de tablas ascendente del libro de texto parecían magia
      En la práctica tiene sentido hacerlo así, porque la eliminación de llamadas de cola no siempre se aplica, pero me habría gustado aprender primero desde la perspectiva más intuitiva de recursión descendente con caché
    • Cuando la aprendí por primera vez, pensé que si era una función tan llamativa, ¿no debería llamarse memoización con arreglos o memoización de la pila de llamadas? Creo que el nombre “programación dinámica” debería haberse reservado para algo mejor
    • Creo que ver la programación dinámica simplemente como recursión memoizada es un malentendido muy extendido. Si la aprendes así, se vuelve muy difícil entender los problemas de programación dinámica del tipo que llenan un arreglo bidimensional
      Por ejemplo, en la serie “Best Time to Buy and Sell Stock” de LeetCode, un problema como https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... me parece mucho más natural resolverlo llenando un arreglo. Nunca lo he resuelto con recursión, y tampoco sé bien si existe una solución recursiva natural
      El enlace anterior es el III, pero para alguien que empieza, comenzar por el primer problema https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... es una buena introducción a la programación dinámica
    • Decir que “la programación dinámica es simplemente caching/memoización” es parecido a decir que “invertir es simplemente comprar algo y venderlo después”. Aunque técnicamente pueda ser cierto hasta cierto punto, omite demasiado la complejidad y dificultad del tema, así que puede sonar más ridículo que revelador

  • El origen del nombre “programación dinámica” viene de su inventor, Richard Bellman. En 1950, en RAND, estaba buscando un nombre para un proceso de toma de decisiones en múltiples etapas, y se dice que el entonces secretario de Defensa Wilson odiaba de forma patológica la palabra “investigación”, y que había que evitar aún más la palabra “matemáticas”
    Bellman necesitaba un nombre que ocultara a Wilson y a la Fuerza Aérea que en RAND en realidad estaban haciendo matemáticas. Así que eligió “programming”, porque trataba de planificación, toma de decisiones y pensamiento, pero “planning” no era conveniente por varias razones; y le agregó “dynamic”, que tiene un significado preciso en la física clásica, para capturar el concepto de múltiples etapas y cambio en el tiempo
    También le gustaba que “dynamic” fuera difícil de usar con un sentido negativo como adjetivo, y como era un nombre al que a un congresista le resultaría difícil oponerse, se dice que usó dynamic programming como nombre general para sus actividades
    Fuente: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

  • Me gusta que este artículo primero revele el problema de forma recursiva, luego agregue caché gradualmente y, al final, reduzca el tamaño de la caché a lo estrictamente necesario
    A menudo he intentado ir directo a una solución de programación dinámica y me he quedado atascado, o he tenido que hacer un esfuerzo excesivo para lograr que funcionara. De ahora en adelante pienso obligarme a seguir los pasos en orden

    • En mi experiencia, si enseñas programación dinámica directamente, se siente como un acertijo. Si vas por etapas, explicas por qué se usa una tabla y conectas ese concepto con el caching, se entiende mucho mejor

  • Una aplicación genial de la programación dinámica es el alineamiento por pares de secuencias de nucleótidos/proteínas
    https://en.wikipedia.org/wiki/Sequence_alignment
    https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
    https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

    • Creo que estos algoritmos son algunos de los más importantes en bioinformática/biología. Su ámbito de aplicación es muy amplio

  • Tuve un profesor de algoritmos muy bueno, que había estudiado en UCLA. Su clase sobre programación dinámica fue excelente: primero empezaba con un problema cuya solución simple tenía complejidad temporal exponencial, luego dividía el problema en problemas más pequeños para bajar la complejidad a un nivel polinomial y, finalmente, aplicaba memoización para reducirla a lineal.
    Ojalá recordara cuáles eran los problemas que usó entonces.

    • Entre los candidatos están la sucesión de Fibonacci, el problema del cambio de monedas, el problema de la mochila 0/1, la multiplicación en cadena de matrices, la subsecuencia común más larga, la subsecuencia creciente más larga, problemas de caminos más cortos como Floyd-Warshall y la distancia de edición (distancia de Levenshtein).
      Todos son ejemplos representativos en los que la solución ingenua es ineficiente y la programación dinámica los mejora mucho.
    • En el artículo también dejé anotados algunos, y son problemas que suelen verse en clases o prácticas. Por ejemplo, subsecuencia común más larga, subcadena común más larga, line warp, suma de subconjuntos, partición y problema de la mochila.
      Para más ejemplos, se puede ver https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
    • Además de los problemas que mencionaron otras personas, también podría haber sido un problema de planificación. Por ejemplo, optimizar N eventos que se solapan en el tiempo, horarios de cursos o procesos de CPU según algún criterio como el rendimiento.
      Tengo entendido que si se agregan restricciones especiales como “estas dos materias deben tomarse juntas”, se vuelve mucho más complejo y difícil de manejar que una programación dinámica común.
    • ¿Habrá sido alguien que estudió en UCLA con Kang?

  • Como parece que el sitio original no aguanta el tráfico, dejo un enlace archivado:
    https://web.archive.org/web/20240114111200/https://qsantos.f...

  • Gracias a la programación dinámica se pudo calcular la cantidad de posiciones legales de Go, y el valor era un número de 171 dígitos.
    El método ingenuo tarda 3^(n^2) porque revisa todas las posiciones posibles en un tablero de Go de n×n, pero la programación dinámica prácticamente elimina una dimensión y reduce la complejidad temporal a O(n^5 * 5.4^n) y la complejidad espacial a O(n * 5.4^n).
    https://tromp.github.io/go/legal.html
    https://tromp.github.io/go/gostate.pdf

  • El nombre “Dynamic Programming” puede sonar raro porque aquí “programming” no se refiere al campo de la programación. En este caso tiene un sentido más cercano a la optimización, como en programación lineal.
    La programación dinámica puede verse como un método para resolver problemas de decisión en tiempo discreto, es decir, elegir la secuencia óptima {a_t} que maximiza \sum_t u_t(a_t) bajo restricciones. Define la función de valor V* como V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) }, reduciendo mucho la dimensión del problema de optimización.

    • De hecho, el origen oficial del nombre https://en.wikipedia.org/wiki/Dynamic_programming#History es bastante gracioso. Bellman dijo que le gustaba “dynamic” porque era un adjetivo imposible de usar con sentido negativo, y que era un nombre al que ni siquiera un congresista podía oponerse.
    • Cuando otras personas usan la expresión “programación dinámica”, a veces se siente como una ostentación para parecer inteligentes. En realidad, solo están usando un enfoque natural e intuitivo al darse cuenta de que el problema puede dividirse en subproblemas cada vez más pequeños, pero lo dicen como si hubieran “usado” alguna técnica especial.
    • Es interesante que antes algo como calcular cosas, como en problemas de optimización, dominaba mucho más la idea de qué hacer con las computadoras. Hoy en día, la mayoría de lo que se hace es almacenar y consultar datos, y hacer networking; aunque haya cálculo dentro de eso, suele sentirse bien encapsulado.
    • La palabra “optimización” también genera malentendidos parecidos. Una vez tomé una clase de ciencias de la computación llamada “optimization” y esperaba algo completamente distinto.
    • Si vamos todavía más atrás, “programming” describe exactamente este concepto. Lo que hoy llamamos “programación” en realidad es escritura de código, y puede dividirse en varias ramas como programación funcional, declarativa y procedural. Bajo ese paraguas entra mucho más que eso.

  • Al oír “programación dinámica”, ¿está mal pensar simplemente en memoización? Quizás lo que falta sea dividir el problema de forma inteligente para poder usar memoización.

    • La memoización es una técnica más general. Muchas veces consiste simplemente en cachear resultados ya calculados por si se necesitan de nuevo más adelante.
      La programación dinámica se parece más a una memoización sistemática. Se resuelven subproblemas cada vez más grandes hasta llegar a la solución del problema completo. El término “algoritmo inductivo” también encaja en cierta medida, porque un algoritmo típico de programación dinámica se parece, en la práctica, a una demostración por inducción matemática. Lamentablemente, ese término ya tiene otros significados.
    • Yo enseño la programación dinámica exactamente así. Primero se resuelve de forma recursiva y luego se agrega memoización. A esto se le llama top-down.
      Después, al ver que la recursión y la memoización tienen sobrecarga, si construyes la tabla de abajo hacia arriba y eliminas las llamadas recursivas, eso se convierte en programación dinámica.
    • En mi enfoque, la memoización es el paso 2 de 3 de la programación dinámica. El paso 1 es encontrar un algoritmo recursivo; el paso 2, la memoización; el paso 3, convertirlo en iterativo/bottom-up y, si es posible, hacer una optimización de espacio como paso 3b.
      El paso 3 es la parte más característica de la programación dinámica, pero creo que detenerse en el paso 2 también puede llamarse programación dinámica. Solo que no es tan eficiente como podría ser. Dicho de otro modo, la memoización es caching, y el paso 3 consiste en preguntarse si hay una forma de llenar ese caché de antemano.
    • También hay soluciones de programación dinámica que no se basan en memoización. Por ejemplo, en el problema de encontrar la subcadena común más larga de dos cadenas, solo se necesitan una vez las celdas de la izquierda y de arriba de la tabla, así que la memoización no ayuda mucho.
      En general, si los subproblemas se superponen mucho y la solución óptima de un subproblema debe formar parte de la solución óptima global, hay una oportunidad para usar programación dinámica. Decir que solo la memoización es programación dinámica se parece a decir que solo las tablas hash son tipos abstractos de datos.
    • Según mi criterio, pensarlo así está mal. Para empezar, hay un contraejemplo obvio: la memoización puede usarse fuera de la programación dinámica. A la inversa, la mayoría de los algoritmos de programación dinámica pueden implementarse guardando resultados en una tabla y luego buscando en esa tabla la mejor respuesta.
      La memoización es, básicamente, una estrategia para hacer más rápido un algoritmo.

  • Terminar el Advent of Code de este año fue divertido. Está claro que el día 1, especialmente la parte 2, fue mucho más difícil que en años anteriores, y escribí sobre eso en https://blog.singleton.io/posts/2024-01-02-advent-of-code-20..., pero no queda claro solo comparando las estadísticas actuales de 2022 con las actuales de 2023. Eso se debe a que la gente tuvo un año más para resolver los puzzles de 2022.
    Al traer las estadísticas de 2022 del 14 de enero de 2023 https://web.archive.org/web/20230114172513/https://adventofc..., la diferencia era bastante grande. Al graficar las estadísticas de finalización de la parte 2 https://blog.singleton.io/static/imgs-aoc23/completion.png, el tamaño del grupo inicial del día 1 era similar, pero 2023 parece claramente más difícil que 2022 hasta el día 15.
    La proporción de personas que resolvieron la parte 1 pero no la parte 2 https://blog.singleton.io/static/imgs-aoc23/ratios.png también es mucho más alta en muchos días de 2023, lo que sugiere que fueron especialmente difíciles el día 5, el día 10, el día 12 y la parte 2 del día 22.

    • Los primeros Advent of Code eran divertidos y, hasta antes de la parte final, uno podía aguantar sin técnicas demasiado sofisticadas. Después se volvieron más difíciles y menos divertidos, así que los dejé y ya no volví a tocarlos.
    • Este año no avancé mucho en Advent of Code por falta de tiempo, pero quizás lo retome más adelante.
      Eso sí, me sorprendió lo difícil que fue la parte 2 del día 5. La resolví sin rendirme, pero me preguntaba si no habría pasado por alto algo obvio y la había resuelto de una forma excesivamente complicada; me tranquiliza saber que en realidad era un problema bastante desafiante.
    • Es solo mi experiencia personal, y también puede haber influido que lo intenté en un lenguaje distinto al que uso normalmente, pero creo que la parte 2 del día 1, más que difícil, tenía una descripción del problema inadecuada.
      Como ejemplos se daban two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen, pero faltaba un ejemplo clave como oneight. Sin ejemplos así, era difícil determinar con precisión cómo había que hacer las sustituciones de valores.
    • Para sumar a esta discusión, tengo un script que muestra el avance por día. Al ver las últimas dos columnas, queda claro lo implacable que fue 2023 en comparación con 2022, especialmente al principio.
      En 2022, durante los primeros días, la mayoría siguió participando; en muchos días la retención superó el 80%, y casi todos resolvieron ambas partes. En cambio, en el día 1 de 2023, entre quienes resolvieron la parte 1, solo el 76% llegó a resolver también la parte 2, y mucha gente abandonó en los días 3 y 5.
      Curiosamente, los últimos días no son tan bajos, lo cual puede explicarse porque el Advent of Code de 2023 es más reciente que el de 2022. Mi interpretación es que ese grupo está formado por personas que, independientemente de la dificultad, superan todos los desafíos hasta cierto punto, mientras que muchas otras abandonan cuando sienten que consume demasiado tiempo.