PROGRAMACION DINAMICA

PROGRAMACION DINAMICA
Estructura De Datos II
Ingeniería en sistemas computacionales

Integrantes:
Oscar André Salinas Ballesteros
Nelson Adrián Rangel Rojas
José Carlos Luna García
Alberto LuisSalas

Método General
La programación dinámica se suele utilizar en
problemas de optimización, donde una solución está
formada por una serie de decisiones.
La programación dinámica no utilizarecursividad, sino
que almacena los resultados de los subproblemas en
una tabla, calculando primero las soluciones para los
problemas pequeños.
Con esto se pretende evitar la repetición de cálculos
para problemasmás pequeños.

Método General

La programación dinámica es un método ascendente:
- Resolvemos primero los problemas pequeños (guardando
las soluciones en
una tabla) y después vamos
combinando pararesolver los problemas más grandes.

Método General
La

programación dinámica se basa en el Principio de
Optimalidad de Bellman: cualquier subsecuencia de una
secuencia óptima debe ser, a su vez, unasecuencia óptima.
Para

cada problema deberíamos comprobar si es aplicable el
principio de optimalidad.
Ejemplo.

2

B

9

A

D
3 C



7

Camino óptimo de A a D: A-C-D, de longitud 10

Caminoóptimo de A al siguiente nivel: A-B, de longitud 2, y
después B-D de longitud 9. Total: A-B-D, de longitud 11



¿Cumple el Principio de Optimalidad?

Método
General
Aspectos

a definir en un algoritmode programación dinámica:

1. Ecuación recurrente, para calcular la solución de los problemas
grandes en función de los problemas más pequeños.
2. Determinar los casos base.
3. Definir las tablasutilizadas por el algoritmo, y cómo son
rellenadas.
4. Cómo se recompone la solución global a partir de los valores de
las tablas.

Análisis de tiempos de ejecución
El

tiempo de ejecución depende delas características
concretas del problema a resolver.
En

general, será de la forma:

Tamaño de la tabla*Tiempo de rellenar cada elemento
de la tabla.


Un

aspecto importante de los algoritmos...