Programación Dinamica
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...
Regístrate para leer el documento completo.