Programación Dinamica

El Arte de la Programación Rápida
Programación Dinámica

Problema ejemplo
Vamos a analizar la técnica de Programación dinámica a través de un ejemplo. Calcular los caminos más cortos entre todoslos pares de nodos de un grafo.

EAPR - EPS - UAM

2

Problema ejemplo
1 3 5

2 6 4 Medimos longitud de caminos
EAPR - EPS - UAM

1 2 3 4 5 6

1 0 2 1 2 2 3

2 2 0 1 1 2 2

3 1 1 01 1 2

4 2 1 1 0 2 1

5 2 2 1 2 0 1

6 3 2 2 1 1 0
3

Problema ejemplo
1 5 2 1 4 9 3 3 17 4 5 2 6 1 0 8 3 9 7 9 2 8 0 5 1 9 10 3 3 5 0 6 4 6 4 9 1 6 0 10 9 5 7 9 4 10 0 2 6 9 10 6 9 2 0

12 3 4 5 6

Medimos costo de caminos
EAPR - EPS - UAM 4

Primera aproximación: backtracking
No, no otra vez!!!! ;) ¿Cuál es el espacio de búsqueda?
1-3-2

1-2
1-3-4-2

1-3

1-3

...Cada camino desde 1-2 a fin me da una combinación de caminos desde cada nodo a todos los demás.
5

...
5-6
5-3-2-4-6

fin

EAPR - EPS - UAM

Primera aproximación : backtracking
Funciona,pero esta solución es muy ineficiente. Rápidamente se puede ver que, aún si el grafo es no dirigido, el algoritmo es proporcional a n!
Para n=10, ya tengo un orden de 106 elementos que procesar...Problema: vuelvo a calcular lo mismo una y otra vez:
1-3-2

1-2
1-3-4-2

1-3

1-3

¡Los subárboles son iguales!
EAPR - EPS - UAM 6

Idea: recordar resultados parciales
ProgramaciónDinámica: técnica para implementar eficientemente algoritmos recursivos por medio del almacenamiento de resultados intermedios

EAPR - EPS - UAM

7

Caminos más cortos con P.D.
Ordeno (numero) losnodos
(ya estaba hecho ☺) pienso algoritmo recursivo:
En cada nivel de recursión k, considero todos los caminos que pasan solo por nodos con índice menor que k. De hecho, ni siquiera necesitamos quesea recursivo!

EAPR - EPS - UAM

8

Caminos más cortos con P.D.
Algoritmo:
Para cada nodo intermedio k (entre 1 y n)
Para cada nodo de salida i
Para cada nodo de llegada j
Veo si...