Diseño y análisis de algoritmos
Técnica de diseño Programación Dinámica II
Temario
• Técnica de diseño Programación Dinámica– Introducción– Aplicaciones
– Multiplicación de Matrices
– Caminos mas cortos en grafo
– Arboles de búsqueda óptimos
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuenciaProblema:• Se desea calcular el producto matricial:
• Por cada par de matrices pxq y qxr, se reqieren pqr multiplicaciones escalares• Al ser el producto asociativo, se tienen varias fomas de realizar una multiplicación
de una cadena de matrices.• Ejemplo: se quiere calcular el producto de ABCD, de las matrices
Se pueden asociar de cinco formas distintas:
nMMMMM .....321
343389895513 DCBA
El orden no es despreciable, pues el caso más eficiente es casi 19 veces más rápido que el peor.
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuenciaProblema:• El problema consiste entonces
• Insertar los paréntesis de todas las formas posibles• Calcular la cantidad de productos necesarios• Obtener el menor entre todos ellos
• La cantidad de formas posibles T(n) de insertar paréntesis para n matrices, se puede deducir:• Cortando la secuencia en dos subsecuencias, entre la i – ava y la (i+1)- ésima
matriz:
Entonces se tienen T(i)T(n-i) formas distintas• Como i puede tomar valores entre 1 y n-1, la cantidad está dada por la
siguiente recurrencia
).....)(...( 121 nii MMMMMM
Números llamados de Catalán.
1
1
)()()(n
i
inTiTnT
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuenciaProblema:• Los números de Catalán crecen exponencialmente
• De hecho puede demostrarse que;
• Por ejemplo: n 1 2 3 4 5 10 15 T(n) 1 1 2 5 14 4862 2674440
• Aplicación del principio de optimalidad:Si el mejor modo de realizar el producto exige dividir inicialnente entre las matrices i e (i+1)-ésima, los productos
nii MMyMMM ........ 121
deberán ser realizados de forma óptima, para que el total también sea óptimo.
1
221)(
n
n
nnT
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuencia• Método
• Construir una matriz , 1<=i<=j<=n, (triangular superior) dondecorresponde a la mínima cantidad de productos necesarios para la parte
del producto total. Por lo que la solución viene dada en • Para construir la matriz, se deben guardar las dimensiones de las Mi 1<=i<=n
en un arreglo d, [0..n], de forma que Mi tiene dimensiones • La diagonal s de contiene los tales que j-i=s:
• Este último caso representa que para calcular , se intentan todas las posibilidades y se escoge la mejor.
][ ijm
]..1[),(min:1
]1..1[,:1
]..1[,0:0
1,11
,
111,
snidddmmmns
nidddms
nims
sikisiiiksiki
sii
iiiii
ii
ijm
jii MMM .....1
nm1
ii dd 1
][ ijm ijm
siii MMM .....1
)...)(...( 211 sikkkii MMMMMM
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuencia• De forma más compacta si i<>j y i <j
• Para el ejemplo anterior: ,d=(13,5,89,3,34)
)(min 1,1 jkijkikjki
ij dddmmm
343389895513 DCBA
Funcion parentOpt(d[0..n];salida m[1..n,1..n],mk[1..n,1..n]) {m contiene el número de multiplicaciones, mk[i,j] guarda el índice k para el que se alcanza el mínimo al calcula m[i,j]}Variables i,j,r,k,q:enteroInicio Para i:= 0 a n hacer m[i,i]:=0; Fin-ParaPara r:= 2 a n hacer Para i:= 1 a n-r+1 hacer j:=i+r-1 m[i,j]=max; {infinito} Para k:= i a j-1 hacer q:=m[i,k]+m[k+1,j]+d[i-1]*d[k]*d[j] si q< m[i,j] entonces m[i,j] := q mk[i,j]:=k FIN-SI FIN-para FIN-para FIN-parafin
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuencia• Implementación
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuencia• Solución en tiempo razonable , al menos polinomial, aunque necesita tres loops
anidados, por lo que
• Queda abierto el problema de hacer un nuevo algoritmo, basado en la matriz mk, indicar en qué orden se multiplican las matrices.
)( 3nO
Técnica de diseño Programación Dinámica
Problema caminos mínimos en un grafoProblema:• Calcular los caminos de costo mínimo o mínima longitud entre todos los pares de
nodos de un grafo dirigido, sin ciclos y pesos positivos.
• Principio de Optimalidad:• Si es un camino de costo mínimo o largo mínimo del
nodo a , entonces:
• es un camino de costo mínimo o largo mínimo del nodo a • es un camino de costo mínimo o largo mínimo del nodo a
• Aplicación del Principio :• Si k es el nodo intermedio de mayor índice en el camino óptimo de i a j,
entonces el subcamino de i a k es un camino óptimo, que además, sólo pasa por nodos de índice menor que k . Lo mismo sucede con el subcamino de k a j
nkk iiiii ...,,..., ,1,21
1i ni
kiii ,...,21 1i ki
nk iii ,...,21 1ki ni
Técnica de diseño Programación Dinámica
Problema caminos mínimos en un grafo• Sea C(i,j) el costo o largo de un arco (i,j) . Si no existe, infinito. Sea C(i,i)=0;• Sea Dk(i,j) la longitud o distancia del camino más corto o de costo mínimo del
nodo i al j que no pasa por ningún nodo mayor que k• Sea Dk(i,j) la longitud del camino más corto de i a j. Entonces:
Técnica de diseño Programación Dinámica
Problema caminos mínimos en un grafo• En resumen:
• Se tiene la siguiente ecuación recursiva que define el método de PD.
• Ejemplo:
1
2
4
3
15
25
15
15
55
30
40
50
0 5 -- 2550 0 15 530 40 0 1515 -- 5 0
0DG0 5 -- 2550 0 15 530 35 0 1515 20 5 0
1D0 5 20 1050 0 15 530 35 0 1515 20 5 0
2D
0 5 20 1045 0 15 530 35 0 1515 20 5 0
3D
5
0 5 15 1020 0 10 530 35 0 1515 20 5 0
4D
Funcion floyd(G[1..n,1..n]): [1..n,1..n]Variables i,j,k:entero; D[1..n,1..n] InicioD:=G Para k := 1 a n hacer Para i := 1 a n hacer Para j := 1 a n hacer D[i,j]:=min(D[i,j], D[i,k]+ D[k,j]) FIN-para FIN-para FIN-para devolver Dfin
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuencia• Implementación, algoritmo Foloyd, muy simple y conocido
Técnica de diseño Programación Dinámica
Problema multiplicación de matrices en secuencia• Solución en tiempo razonable , al menos polinomial, aunque necesita tres loops
anidados, por lo que
• El tiempo es comparable con n veces Dijsktra, pero por simplicidad se prefiere Floyd.
• Este algoritmo sólo encuentra las distancias entre cada par de nodos. Para obtener los nodos que implementen esa distancia, es necesario recordar para cada (i,j) cuál es al k que proveyó la mínima distancia.
• Ejercicio, implementar una solución en base a una matriz auxiliar P, que se modifica cada vez que se modifica D:
Cambiar línea min{}, por si D[i,j] > D[i,k] + D[k,j] entonces D[i,j]:=D[i,k]+ D[k,j] P[i,j]:=k finSi
)( 3nO
0 0 4 24 0 4 00 1 0 00 1 0 0
P
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimosProblema:• Se usará un recorrido “en orden” del árbol para realizar la búsqueda. La estructura
cumple que todo nodo tiene una clave mayor que los de su subarbol izquierdo y menor que los de su subarbol derecho.
• Se tiene un conjunto de claves distintas
• Pueden ser claves alfanuméricas(orenadas ascendentemente), almacenadas en un arbol binario de búsqueda.
• Se conoce la probabilidad , con la que se pide buscar la clave y su información asociada.
• Se conoce también la probabilidad , de búsqueda de una clave inexistente situada entre y
• Se tiene que
• Por lo que el problema radica en construir un árbol binario de búsqueda para almacenar las claves, que minimice el número medio de comparaciones para encontrar una clave o garantizar que no está.
nwww ...21
]..1[, nipi iw
n
ii
n
ii qp
01
1
]..0[, niqi iw 1iw
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos• Recordar que la profundidad de la raiz es 0, la de sus hijos 1, ...• Si se construye un árbol donde la clave está en un nodo de profundidad ,
1<=i<=n, entonces se necesitan comparaciones para encontrarla.• Si con probabilidad , 0<=i<=n , se busca una clave que no está en el árbol,
pero que en caso de estar , ocuparía un nodo de profundiadad , entonces se necesitan para asegirar que no está.
• Por lo tanto el número medio de comparaciones necesarias para encontrar una clave o garantizar que no está (función a minimizar) es:
iw
n
iii
n
iii dqdpC
01
)1(
id1id
iq
id
id
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos• Para el ejemplo:
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos• Solución de programación dinámica:
• Principio de Optimalidad: Todos los subárboles de un árbol óptimo son óptimos con respecto a las
claves que continen.• Considerando un subárbol óptimo que contenga las claves• La probabilidad de que una clave buscada esté o debiera estar en ese
subárbol es:
• Se denotará al número medio de comparaciones efectuadas en un subárbol óptimo que contiene las claves durante la búsqueda de una clave en el árbol principal (por convención ).
• Supongamos ahora que ocupa la raíz de ese subárbol.• Sea entonces el número medio de comparaciones efectuadas en ese
subárbol durante la búsqueda de una clave en el árbol principal.
jii www ,...,, 21
j
ikk
j
ikkij qpm
1
ijC
jii www ,...,, 21
0iiC
kwkijC
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos• Entonces:
• , es el número medio de comparaciones en el subárbol izquierdo.• , es el número medio de comparaciones en el subárbol derecho.• ,es el número medio de comparaciones con la raiz.
• Ahora se trata de escoger la raiz de manera que se minimice
kjkiijkij CCmC 1,
ijC
1, kiC
kjC
ijm
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos
Tipos probP= Arreglo [1..n] real probQ= Arreglo [1..n] real matC=matriz [0..n,0..,n] real matSol=matriz [0..n,0..,n] enteroFuncion abbOPT(entrada p: probP;q: probQ; salida C:matC; rMatSol){C es la matriz de comparaciones media. En cada componente i , j de r se guarda el k para el que C[i,j] resulta mínimo}Variables i,j,k,d:entero min,aux:real m:Matc
Inicio Para i := 0 a n hacer C[i,i]:=0 m[i,i]:=q[i] Para j := i+1 a n hacer m[i,j]:=m[i,j-1]+p[j]+ q[j] Fin-para Fin-para
.....
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos• Implementación
....Para j := 1 a n hacer C[j-1,j]:=m[j-1, j] r[j-1, j]:=j Fin-para{ya están determinados los árboles de 1 nodo}Para d := 2 a n hacer Para j := d a n hacer i:=j-d min:=100000000; Para k := i+1 a j hacer aux:= C[i,k-1]+C[k, j] si aux < min entonces min:=aux;r[i, j]:=k fin-si Fin-para C[i,j]:=m[i, j]+min Fin-para Fin-paraFIN.
Técnica de diseño Programación Dinámica
Problema Arboles binarios de búsqueda óptimos