Programacion dinamica

Programación Dinámica.
¿Qué es la programación dinámica? Se dice que es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de sub-problemas superpuestos ysub-estructuras optimas, como se describirá en un momento.
Richard Bellman invento la programación dinámica en 1953 que se utiliza para optimizar los problemas complejos que pueden ser discretizados ysecuencializados.
En general, se puede resolver problemas con sub-estructuras óptimas siguiendo estos 3 pasos:
1. Dividir el problema en sub-problemas más pequeños.
2. Resolver los problemas demanera optima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construir una solución optima al problema original.
En resumen, la programación hace uso de:* Sub-problemas superpuestos
* Sub-estructuras optimas
* Memorización
La programación toma normalmente uno de los siguientes enfoques:
Top-Down: el problema se divide en sub-problemas, yestos se resuelven recordando las soluciones por si fueran necesarias. Es una mezcla de memorización y recursión.
Bottom-up: todos los problemas que puedan ser necesarios se resuelven de antemano ydespués se usan para resolver las soluciones a problemas mayores. Es ligeramente mejor en consumo de espacio y llamadas a funciones.
Realmente lo que determinara como programación dinámica es laresolución de ciertos problemas y operaciones fuera del ámbito de la ingeniería informática, al igual que a la programación lineal. Se tiene que calcular mejor la solución consecutivamente.
Modelos deprogramación dinámica:
Existen tres modelos diferentes manejados por WINQSB:
1. Problema de la diligencia.
2. Problema de la mochila.
3. Programación de producción e inventarios.
Eltérmino dinámico yace de que la tabla auxiliar se rellena en tiempo de ejecución. No debe confundirse la programación dinámica en el ámbito algorítmico con los lenguajes de programación dinámicos como...