La programación dinámica no es magia negra

La programación dinámica no es magia

• La programación dinámica es una técnica usada para resolver problemas complejos, abordándolos al dividirlos en problemas más pequeños.
• Esta técnica es algo natural, y muchos algoritmos comunes son en realidad aplicaciones de programación dinámica a problemas específicos.
• Para ayudar a entender la programación dinámica, se ofrece una introducción más sencilla y una explicación detallada.

Queja

• La ingeniería de software suele ser terrible para poner nombres.
• Términos como 'bootstrap', 'daemon', 'cascading style sheets', 'cookie' e 'inteligencia artificial' son ambiguos o pueden inducir a error.
• El término 'programación dinámica' tampoco tiene relación con lo "dinámico" en sí mismo, y en realidad es una idea usada en el diseño de algoritmos.

Caché básica

• Cuando se intenta resolver un problema dividiéndolo en pequeños subproblemas similares, puede ser necesario resolver los mismos subproblemas muchas veces.
• Usando el ejemplo de la secuencia de Fibonacci, si se implementa con una función recursiva simple, se termina repitiendo el mismo cálculo varias veces.
• Se puede evitar el cálculo duplicado guardando los resultados en caché (o usando memoización).

Caché optimizada

• Al usar memoización, se mantiene la recursión, pero se calcula lo necesario cuando hace falta.
• En cambio, también se puede abordar calculando por adelantado todo lo que se va a necesitar.
• Este método resuelve el problema sin llamadas recursivas, y eso es precisamente la programación dinámica.

Distancia de edición

• La distancia de edición entre dos cadenas es el número mínimo de ediciones necesarias para transformar una cadena en otra.
• La distancia de edición puede calcularse incluyendo sustituciones, inserciones y eliminaciones de caracteres, y esto puede resolverse eficientemente con programación dinámica.
• Hay que encontrar la forma de derivar la solución completa a partir de las soluciones de los problemas pequeños.

Advent of Code, Día 12

• En el problema de Advent of Code del 12 de diciembre de 2023, hay que resolver un nonograma 1D.
• Puede resolverse con fuerza bruta, pero eso tiene complejidad exponencial.
• En su lugar, se puede aplicar programación dinámica para resolverlo de forma eficiente.

Conclusión

• La programación dinámica no es fácil, pero tampoco está fuera del alcance de la mayoría de los programadores.
• Si se entiende cómo dividir un problema en subproblemas, se puede usar la memoización en muchas situaciones, y eso representa una gran mejora frente a una implementación ingenua.
• Dominar la programación dinámica permite entender toda una clase de algoritmos, comprender mejor los trade-offs y habilitar otras optimizaciones.

Opinión de GN⁺

• La programación dinámica es una técnica importante para resolver problemas complejos de forma eficiente, ya que mejora mucho el rendimiento al reducir cálculos duplicados mediante el almacenamiento en caché de soluciones a subproblemas, en lugar de depender de un enfoque puramente recursivo.
• Este artículo es muy útil para ingenieros de software principiantes que quieran entender los conceptos básicos de la programación dinámica.
• Los ejemplos de la secuencia de Fibonacci y la distancia de edición ayudan a comprender el concepto de programación dinámica y ofrecen un buen punto de partida para aplicarlo a la resolución de problemas reales.

[GN⁺]

Opiniones en Hacker News

• Es bueno que el artículo explique los algoritmos de programación dinámica (DP) como caché de recursión.

  • Encontrar una solución recursiva es un punto de partida ideal para encontrar una solución de DP.
  • Memorizar una solución recursiva (memoization) puede ayudar mucho a mejorar la velocidad.
  • Lo importante no es que haya una gran cantidad de subproblemas en el árbol de llamadas, sino que debe haber una cantidad relativamente pequeña de subproblemas únicos.

• Gusta el enfoque del artículo de tratar primero el problema de forma recursiva, luego agregar caché gradualmente y después reducirlo hasta el tamaño de caché necesario.

  • Ha pasado por experiencias en las que intentar encontrar directamente una solución de programación dinámica lo bloqueó o requirió un gran esfuerzo.
  • En adelante intentará obligarse a seguir un enfoque paso a paso.

• Una aplicación genial de la programación dinámica es la alineación por pares de secuencias de ácidos nucleicos/proteínas.

  • Por ejemplo, alineación de secuencias, algoritmo de Needleman–Wunsch, algoritmo de Smith–Waterman, entre otros.

• Comparte una experiencia sobre un profesor de algoritmos extraordinario.

  • El profesor estudió en UCLA y su clase sobre programación dinámica fue excelente.
  • Empezó con un problema simple pero de complejidad exponencial, dividió el problema en problemas pequeños y redujo la complejidad a polinómica, y luego aplicó memoization para bajarla a complejidad lineal.
  • Le gustaría recordar cuáles fueron los problemas utilizados.

• Comparte un enlace al texto Dynamic Programming Is Not Black Magic.

  • Ese texto se volvió difícil de acceder debido al gran tráfico (hug of death).

• Una persona que aprendió a programar sobre todo por su cuenta comenta que, si en una entrevista de trabajo le hubieran pedido usar programación dinámica, no habría sabido hacerlo.

  • Por suerte eso no ocurrió, y como conocía la técnica la usó en varias entrevistas.

• El nombre "programación dinámica" puede no parecer provenir del campo de la programación.

  • En realidad está relacionado con optimización y es una forma de resolver problemas de decisión en tiempo discreto.
  • La programación dinámica es una manera de reducir enormemente la dimensión de un problema de optimización definiendo una función de valor V*.

• Se plantea la duda de si está mal pensar solo en "memoization" al escuchar "programación dinámica".

  • Tal vez lo que falta es dividir el problema de forma inteligente para poder usar memoization de manera efectiva.

• La programación dinámica no es magia negra; lo difícil es demostrar que se puede programar dinámicamente y probar su corrección.

  • Al igual que con los algoritmos voraces, se necesita una demostración formal usando inducción matemática.

• Para dominar la programación dinámica, recomienda el libro de algoritmos DPV y el curso de Udacity de Georgia Tech.

  • Se puede aprender programación dinámica practicando al resolver problemas.