![Page 1: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/1.jpg)
Diseño y análisis de algoritmos
Técnica de diseño Programación Dinámica I
![Page 2: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/2.jpg)
Temario
• Técnica de diseño Programación Dinámica– Introducción– Aplicaciones
– Problema de la mochila, valores enteros
– Camino más corto en grafo por etapas
![Page 3: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/3.jpg)
Técnica de diseño Programación Dinámica Introducción
• Estos algoritmos se usan típicamente en problemas de optimización, donde hay que encontrar un máximo o un mínimo.
• Al igual que los algoritmos greedy, permite resolver problemas, tomandouna secuencia de decisiones.
• A diferencia de esquema greedy que toma localmente la decisión, en forma prematura, PD, produce varias secuencias de decisiones y sólo al final,se sabe cuál es la mejor de ellas.Ejemplos:
• Dado un conjunto dado de monedas de distinta denominación, ¿cuál es laMínima cantidad de monedas necesarias para pagar x pesos?• Problema de la mochila, con valores enteros.• Encontrar el camino más corto en un grafo.• Multiplicación de una secuencia de matrices.• Arboles de búsqueda óptimos.
![Page 4: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/4.jpg)
Técnica de diseño Programación Dinámica Introducción
• Es similar al esquema dividir y conquistar en cuanto a que PD determina la solución óptima de un problema de n variables descomponiéndola en n etapas o subproblemas.
• Está basada en el principio de optimalidad de Bellman: “Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones queresualeve un problema, también debe ser óptima respecto del subproblema que resuelve.”
• Suponienedo que un problema se resuelve, tras tomar una secuencia de d1, d2,.. dn de decisiones. Si hay d opciones posibles, para cada una de las decisiones, una técnica de “fuerza bruta”, debería explorar secuencias posibles de decisiones.(explosión combinatoria) • La técnica de PD, evita explorar , todas las secuencias posibles , por medio dela resolución de subproblemas de tamaño creciente y el almacenamiento en una tabla de soluciones óptimas de esos subproblemas, facilitando la solución de losproblemas más grandes. Usa un enfoque Bottom UP.
nd
![Page 5: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/5.jpg)
Técnica de diseño Programación Dinámica Introducción
• Debido a que la naturaleza de los subproblemas depende de cada problema de optimización , los detalles de la resolución deben ser adecuados a cada problema, sin embargo se pueden definir los pasos generales a seguir:• Sea Eo , el estado inicial del problema. • Sea , el conjunto de valores de decisión posibles para ladecisión d1.• Sea el estado del problema tras la elección del valor • Sea una secuencia óptima de decisiones respecto al estado
• Principio de Optimalidad:Una secuencia óptima de desiciones respecto a Eo es la mejor de las secuencias de decisión
• Generlizando, se puede aplicar el mismo procdimiento, a cualquier subsecuencia de decisiones , partiendo comoestado inicial Ek-1.
Una solución dinámica para este problema, simbolizado como (k,l) , debe expresarse en términos de los valores de decisión existentes, para la decisión dk y el subproblema (k+1,l) ,resultante de aplicar cada valor de decisión.
},.....,{ 11111 nvvD
iS1
11 1, niv i iE1
iE1
111 1},,{ niSv ii
nlkdd lk 1,,...,
![Page 6: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/6.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1Recordando, problema:Se tienen n objetos y una mochila (cada objeto i tiene un peso y un valor ;la mochila tiene una capacidad W). Se pretende encontrar la manera de cargar la mochila de forma que maximice el valor de lo transportado, respetando su capacidad máxima.Esta vez, los objetos x van completos o no van.
Es decir encontrar valores tal que,
se maximice sujeto a la restricción
Los pesos y la capacidad son enteros positivos. Los beneficios , pueden ser reales positivos.Ejemplo: n=3 y W=15, Tomando la estrategia greedy del mayor beneficio/peso.Se obtiene la solución , con beneficio 64.Sin embargo, la mejor solución es ,con beneficio 78 La estrategia greedy no encuentra la solución óptima para el problema de la mochila 0-
1
iw iv
]1,0[ix
n
iiivx
1
Wwxn
iii
1
iw W
iv
)1,1,0(),,( 321 xxx)0,1,1(),,( 321 xxx
)5,6,9(),,(),24,40,38(),,( 321321 wwwvvv
![Page 7: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/7.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1El nuevo problema es mochila (k,l,W)Encontrar valores tal que,
se maximice sujeto a la restricción
con • El problema de la mochila 0-1 es mochila(1,n,W) • Principio de optimalidad:
Sea una secuencia óptima de valores 0-1 para • Si entonces forman una secuencia óptima para el
problema mochila(2,n,W).• Si entonces forman una secuencia óptima para el
problema mochila(2,n,W- ).
ix
likxi ],1,0[
l
kiiivx Wwx
l
kiii
01 ynyy ,...,1 nxx ,...,1
nyy ,...,2
11 y nyy ,...,2
1w
![Page 8: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/8.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Principio de optimalidad, lo mismo se cumple:
Si una secuencia óptima del problema mochila(1,n,W), entonces paratodo :• Si es la secuencia óptima de
• Si es la secuencia óptima de
nyy ,...,1
jyy ,...,1
j
iii xwjmochila
1
,,1
njj 1,
nj yy ,...,1
j
iii xwWnjmochila
1
,,1
![Page 9: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/9.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Ecuación recursiva hacia “adelante”
Si es el beneficio o la ganancia total de una solución óptima de mochila(j,n,W), entonces ,
Dependiendo de que el objeto j-ésimo entre o no en la solución (nótese que sólo puede entrar si ). Además, para cualquier capacidad W. Notar que aunque la ecuación recursiva es hacia adelente, el cálculo se realiza hacia atrás.
• Ecuación recursiva hacia “atrás” Si es el beneficio o la ganancia total de una solución óptima de mochila(1,j,W), entonces ,
Dependiendo de que el objeto j-ésimo entre o no en la solución (nótese que sólo puede entrar si ). Además, para cualquier capacidad W. Notar que aunque la ecuación recursiva es hacia atrás, el cálculo se realiza hacia adelante.
)(Wg j
})(),(max{)( 11 jjjjj vwWgWgWg
0 jwW0)(1 Wgn
)(Wg j
})(),(max{)( 11 jjjjj vwWgWgWg
0 jwW 0)(0 Wg
![Page 10: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/10.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Ambas ecuaciones permiten calcular , que es el valor de una solución
óptima de mochila(1,n,W), entonces , tanto la recurencia hacia delante como hacia atrás permitenescribir un algoritmo recursivo de forma inmediata:
)(Wgn
Funcion mochila1(w,v:[1..n];W:entero):enteroInicio g(n,W)Fin;Funcion g(j,c:entero):entero;Iniciosi j= 0 entonces devuelve 0 sino si c < w[j] entonces devuelve g(j-1,c) sino si g(j-1,c)>= g(j-1,c-w[j])+v[j] entonces devuelve g(j-1,c) SINO devuelve g(j-1,c-w[j])+v[j] FIN-SI FIN-SI FIN-SIfin
![Page 11: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/11.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Complejidad del algoritmo
Un problema de tamaño n es reducido a dos subproblemas de tamaño n-1Cada uno de los subproblemas se reduce a otros dos, y así sucesivamente.Recordando la recurrenciaSe tiene un alogoitmo eponenecial, por lo que no se ha ganado nada, con respecto
a la solución de búsqueda exhaustiva o “fuerza bruta”.
• Sin embargo, el número total de subproblemas a resolver no es tan grande: La función tiene dos parámetros: • el primero puede tomar n valores distintos• el segundo, W valores• Luego a lo más hat nxW subproblemas diferentes
• Por lo tanto , la solución recursiva está generando y resolviendo el mismo problema muchas veces.
)(Wgn
)2(1)1(2)( nOnTnT
![Page 12: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/12.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Solución en tiempo razonable
Para evitar la repetición de cálculos, las soluciones de los subproblemas se deben almacenar en una tabla.
• Se ocupa una matriz nxW, cuyo elemento (j,w), almacena • Para el ejemplo anterior
n=3 y W=15
)(wg j
)5,6,9(),,( 321 www
)24,40,38(),,( 321 vvv
})(),(max{)( 11 jjjjj vwWgWgWg
ww1=9w2=6w3=5
![Page 13: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/13.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Implementación no recursiva:
Funcion mochila2(w,v:[1..n];W:entero):[1..n,1..W]Variables c,j:entero;g:[1..n,1..W]InicioPara c:= 0 a W hacer g[0,c]:=0;Para j:= 0 a n hacer g[j,0]:=0;Para c:= 1 a W hacer Para j:= 1 a n hacer si c < w[j] entonces g[j,c]:= g[j-1,c] sino si g[j-1,c]>= g[j-1,c-w[j]]+v[j] entonces g[j,c]:= g[j-1,c] SINO g[j,c]:= g[j-1,c-w[j]]+v[j] FIN-SI FIN-SI FIN-para FIN-paradevuelve gfin
![Page 14: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/14.jpg)
Técnica de diseño Programación Dinámica
Problema de la mochila valores 0-1• Solución en tiempo razonable
Para W no muy grandes
• Puesto que se llena ocupa una matriz nxW, hay dos ciclos anidados, el algoritmo
• Queda abierto el problema de,que al generar la tabla o hacer un nuevo algoritmo, indicar qué objetos van incluidos en la mochila.
• Esta solución funciona si W y los pesos de los objetos son enteros.
)( 2nO
![Page 15: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/15.jpg)
Técnica de diseño Programación Dinámica
Problema costo mínimo de caminos en un grafo multietapaGrafo multietapa:• Es un caso especial de grafo G(V,A), es un grafo dirigido en el que se puede hacer
una partición del conjunto V de vérices en k (k>=2)conjuntos distintos Vi , 1<=i<=k tal que todo arco del grafo (u,v) cumple que y para algún i, 1<=i<=k .
• Los conjuntos V1 y Vk tienen un solo vérice que se llama vértice orígen o y vértice destino d, respectivamente.
• Se considerarán grafos etiquetados, en sus arcos, los cuales pueden representar costos, distancias , etc. Notación: c(u,v), es el “costo” del arco (u,v)
iVu 1 iVu
![Page 16: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/16.jpg)
Técnica de diseño Programación Dinámica
Problema costo mínimo de caminos en un grafo multietapaGrafo multietapa:• El problema es encontarar un camino de costo mínimo, entre o y d • Todo camino de o a d tiene exactamente un vértice en cada etapa Vi , por eso se
dice que cada Vi define una etapa del grafo.
Usando proramación dinámica:• Cada camino entre o y d es una secuencia de k-2 decisiones • La decisión i-ésima: determinar, a partir de un vértice vi de Vi, un arco que tenga vi
como origen y algún nodo de Vi+1 como destino.• Principio de optimalidad: El camino de costo mínimo debe contener subcaminos
de costo mínimo entre otros nodos.
![Page 17: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/17.jpg)
Técnica de diseño Programación Dinámica
Problema costo mínimo de caminos en un grafo multietapa• Ecuación recursiva hacia “adelante”
Sea s(i,j) un camino de costo mínimo C*(i,j) desde el vérice j del conjunto Vi
hasta el vétice de destino d. Entonces:
),(
),1(*djc
jkCSi En otro caso
Adj ),(
21,),1(),(min),(* * kiparaliCljcjiC
Alj
Vj i
),(1
![Page 18: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/18.jpg)
Técnica de diseño Programación Dinámica
Problema costo mínimo de caminos en un grafo multietapa• Ya se obtuvo el costo o distancia más corta entre o y d , falta almacenar las
decisiones hechas en cada etapa : Sea D(i,j) el valor de l que minimizaEntonces el camino de mínimo costo o distancia es:
),1(),( * liCljc
.));...1,1(,2();1,1(;1 321 etcDDvDvv
![Page 19: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/19.jpg)
Técnica de diseño Programación Dinámica
Problema costo mínimo de caminos en un grafo multietapa• Implementación :
Funcion multietapa(G[1..n,1..n];n,k:entero):[1..k] {salida es el camino de k etapas}{Los nodos etán numerados, de manera asecendente en relación a cada etapaEl primer índice de C* y D que identifican la etapa se han suprimido}Variables C arreglo [1..n] real {costos};P arrgelo [1..k] entero;D arreglo [1..n] entero;j,r:enteroInicio C[n]:=0.0; {calculo de C* y D} Para j:= n-1 descendiendo hasta 1 hacer r:= nodo tal que arco (j,r) exista y G[j,r]+ C[r] es mínimo; C[j]:= G[j,r]+ C[r] C[j]:= r FIN-para P[1]=1;P[k]:=n; {construcción del camino} Para c:= 2 a k-1 hacer P[j]:=D[P[j-1]] FIN-paradevuelve Pfin
![Page 20: Diseño y análisis de algoritmos Técnica de diseño Programación Dinámica I](https://reader034.vdocumento.com/reader034/viewer/2022042512/552de2b1550346df7a8b47ff/html5/thumbnails/20.jpg)
Técnica de diseño Programación Dinámica
Problema costo mínimo de caminos en un grafo multietapa
• Si G está representado por una matriz, la búsqueda del arco mínimo se convierte en un recorrido completo, es decir otro for por lo que el algoritmo es
• Sin embargo si se aprovecha la característica de que es multietapa y se implementa con una lista de adyacencia, el primer ciclo es proporcional al grado del vértice j, que se podría estandarizr en a, por lo que el algoritmo quedaría
• Como ejercicio propuesto, queda expresar la solución recursiva hacia atrás y su algoritmo.
)()( nOanO
)( 2nO