DAA - Programación dinámica
La programación dinámica también se utiliza en problemas de optimización. Al igual que el método de divide y vencerás, la programación dinámica resuelve problemas combinando las soluciones de subproblemas. Además, el algoritmo de programación dinámica resuelve cada subproblema solo una vez y luego guarda su respuesta en una tabla, evitando así el trabajo de volver a calcular la respuesta cada vez.
Dos propiedades principales de un problema sugieren que el problema dado se puede resolver mediante la programación dinámica. Estas propiedades sonoverlapping sub-problems and optimal substructure.
Subproblemas superpuestos
De manera similar al enfoque de dividir y conquistar, la programación dinámica también combina soluciones a subproblemas. Se utiliza principalmente cuando se necesita la solución de un subproblema repetidamente. Las soluciones calculadas se almacenan en una tabla, por lo que no es necesario volver a calcularlas. Por lo tanto, esta técnica es necesaria cuando existe un subproblema superpuesto.
Por ejemplo, la búsqueda binaria no tiene subproblemas superpuestos. Mientras que el programa recursivo de números de Fibonacci tiene muchos subproblemas superpuestos.
Subestructura óptima
Un problema dado tiene la propiedad de subestructura óptima, si la solución óptima del problema dado puede obtenerse utilizando soluciones óptimas de sus subproblemas.
Por ejemplo, el problema de la ruta más corta tiene la siguiente propiedad de subestructura óptima:
Si un nodo x se encuentra en la ruta más corta desde un nodo de origen u al nodo de destino v, luego el camino más corto desde u a v es la combinación del camino más corto desde u a x, y el camino más corto desde x a v.
Los algoritmos estándar de todos los pares de ruta más corta como Floyd-Warshall y Bellman-Ford son ejemplos típicos de programación dinámica.
Pasos del enfoque de programación dinámica
El algoritmo de programación dinámica está diseñado utilizando los siguientes cuatro pasos:
- Caracterizar la estructura de una solución óptima.
- Defina de forma recursiva el valor de una solución óptima.
- Calcule el valor de una solución óptima, generalmente de forma ascendente.
- Construya una solución óptima a partir de la información calculada.
Aplicaciones del enfoque de programación dinámica
- Multiplicación en cadena de matrices
- Subsecuencia común más larga
- Problema del vendedor ambulante