Decidir los subproblemas para la programación dinámica

39

He usado la técnica de la programación dinámica varias veces, sin embargo, hoy un amigo me preguntó cómo definiría mis subproblemas, me di cuenta de que no tenía forma de proporcionar una respuesta formal objetiva. ¿Cómo define formalmente un subproblema para un problema que resolvería utilizando la programación dinámica?

algorithms dynamic-programming Daniel Gratzer
fuente
Parece que ninguna de las respuestas existentes (a partir de abril de 2019) es lo suficientemente buena, especialmente para los principiantes. Recomendaría tutoriales en otros sitios.
Apass.Jack

Respuestas:

35

El principio de la programación dinámica es pensar de arriba hacia abajo (es decir, recursivamente) pero resolver de abajo hacia arriba. Entonces, una buena estrategia para diseñar un DP es formular el problema de forma recursiva y generar subproblemas de esa manera.

Suresh
fuente
14
Afirmo que esa es la única estrategia.
JeffE
2
@JeffE Sí, leí y usé tus notas al enseñar mis clases de algoritmos y fue efectivo. Cita: "La dinámica no se trata de completar tablas. ¡Se trata de una recursión inteligente!"
Dai
2
Mi comprensión de cómo enseñar a los PD está fuertemente influenciada por las notas de @ JeffE :)
Suresh
3
También es posible convertir automáticamente un procedimiento recursivo de arriba hacia abajo en un algoritmo de programación dinámico. Cuando esté a punto de regresar, guarde la respuesta en una tabla hash. Al comienzo de cada llamada, verifique si la respuesta ya está en la tabla hash y, de ser así, devuélvala de inmediato. Muchos algoritmos se vuelven fáciles con esta idea. Por ejemplo, con dicha tabla, los algoritmos recursivos en intentos funcionan automáticamente en DAWG. Al almacenar un valor centinela en la tabla al comienzo de una llamada, los mismos algoritmos pueden funcionar incluso en DFA. Los algoritmos en BDD se vuelven muy fáciles de especificar de forma recursiva.
Jules
1
Por último, pero no menos importante, esto puede tener enormes ventajas de rendimiento. Por ejemplo, el algoritmo tradicional de suma de subconjuntos ascendente puede calcular toneladas de entradas de tabla innecesarias. Con este método solo se computarán las entradas de tabla necesarias.
Jules
4

Como señaló @Suresh, una vez que sepa que DP puede resolver su problema (es decir, exhibe una subestructura óptima y subproblemas superpuestos), puede pensar en una solución recursiva de dividir y conquistar.

Por supuesto, dividir y conquistar será muy poco eficiente porque cada subproblema encontrado en el árbol de recursión asociado se resolverá nuevamente, incluso si ya se ha encontrado y resuelto. Aquí es donde DP difiere: cada vez que encuentra un subproblema, lo resuelve y almacena su solución en una tabla. Más tarde, cuando encuentre nuevamente ese subproblema, accederá en su solución en lugar de resolverlo nuevamente. Dado que la cantidad de subproblemas superpuestos generalmente está limitada por un polinomio, y el tiempo requerido para resolver un subproblema también es polinomial (de lo contrario, DP no puede proporcionar una solución rentable), en general se obtiene una solución polinómica.O(1)

Por lo tanto, pensar en una solución de divide y vencerás te dará una idea de lo que puede ser un subproblema para tu problema en particular.

Massimo Cafaro
fuente
1
"subestructura óptima" (lo que sea que eso signifique) probablemente no sea una condición suficiente para la solubilidad de DP. "Subproblemas superpuestos" ciertamente no es necesario.
Raphael
1
La subestructura óptima y los problemas superpuestos están expuestos a problemas que DP puede resolver de manera eficiente. Por supuesto, la subestructura óptima por sí sola no es suficiente para la solubilidad DP. Sin embargo, si no tiene subproblemas superpuestos, puede resolver el problema dividiendo y conquistando con el mismo costo: de hecho, la ventaja de DP sobre dividir una conquista es que cada subproblema se resuelve exactamente una vez cuando se encuentra en el árbol de recursión .
Massimo Cafaro
1
No es mi formulación: la encontrará en "Introducción a los algoritmos" de Cormen, Leiserson, Rivest y Stein y en muchos otros libros de texto sobre algoritmos.
Massimo Cafaro
1
Jup, y la mayoría están al menos parcialmente equivocados. Me complace dar más detalles si publica una pregunta adecuada.
Raphael
1
No estoy seguro de entender correctamente su último comentario. Para mostrar que este tipo de caracterización es incorrecto (no puede ser parcialmente incorrecto: es correcto o incorrecto), simplemente puede mostrar como un contraejemplo, un problema que no muestra una subestructura óptima y subproblemas superpuestos, pero es susceptible de una solución polinomial DP. Pero tenga en cuenta que, en este contexto, eso significa una solución que es probablemente mejor que dividir y conquistar ordinaria.
Massimo Cafaro
2

Mi experiencia es encontrar una manera de "reducir la enumeración redundante con la ayuda de almacenar valores útiles ya enumerados". Por cierto, la programación dinámica es muy popular en el ICPC (Concurso internacional de programación colegial. Cualquiera puede tener sus propios sentimientos sobre DP después de practicar varios problemas de ICPC.

Peng Zhang
fuente