Download - PROGRAMACION DINAMICA
![Page 1: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/1.jpg)
ProgramaciónDinámica
Docente : Lic. Gabriel Solari Carbajal
Universidad Nacional Mayor de San MarcosFacultad de Ingeniería de Sistemas e Informática
Investigación Operativa II
![Page 2: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/2.jpg)
2
INTRODUCCIONLa Programación Dinámica (PD), es una técnica que permite resolver problemas en los cuales se debe tomar no una sino una secuencia de decisiones.
El francés P. Massé en 1946 utilizó un método semejante a la PD, pero no recibió toda la atención que merecía. En 1957 el matemático norteamericano Richard Bellman publica su obra DynamicProgramming, donde describe los fundamentos de la PD.
La facilidad de su metodología ha permitido la resolución de innumerables problemas.
Programación Dinámica
![Page 3: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/3.jpg)
3
FUNDAMENTO DE LA PDDado un problema:
Programación Dinámica
PROBLEMA
![Page 4: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/4.jpg)
4
Este problema se divide en etapas. El número de etapas dependerá de las características del problema:
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
![Page 5: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/5.jpg)
5
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
Se resuelve una etapa cualquiera. Seleccionemos, por ejemplo, la etapa 4:
![Page 6: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/6.jpg)
6
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
La solución óptima se determina de revisar todas las decisiones posibles de la etapa 4:
![Page 7: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/7.jpg)
7
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
La solución de la etapa 4 se utiliza para resolver la etapa 3:
![Page 8: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/8.jpg)
8
La nueva solución óptima se determina de revisar todas las decisiones posibles de la etapa 3 (integrando las soluciones de la etapa 4):
Programación Dinámica
ETAPA2
ETAPA1
ETAPAS3 Y 4
![Page 9: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/9.jpg)
9
Programación Dinámica
ETAPA2
ETAPA1
ETAPAS3 Y 4
La solución de las etapas 3 y 4 se utiliza para resolver la etapa 2:
![Page 10: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/10.jpg)
10
Programación Dinámica
ETAPA1
ETAPAS2, 3 Y 4
La nueva solución óptima se determina de revisar todas las decisiones posibles de la etapa 2 (integrando las soluciones de las etapas 3 y 4):
![Page 11: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/11.jpg)
11
Programación Dinámica
ETAPA1
ETAPAS2, 3 Y 4
La solución de las etapas 2, 3 y 4 se utiliza para resolver la etapa 1:
![Page 12: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/12.jpg)
12
La nueva solución óptima se determina de revisar todas las decisiones posibles de la etapa 1 (integrando las soluciones de las etapas 2, 3 y 4), ésta es la solución del problema original:
Programación Dinámica
ETAPAS1, 2, 3 Y 4
![Page 13: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/13.jpg)
13
PRINCIPIO DE OPTIMALIDAD DE BELLMANEl teorema presentado por Bellman, denominado Principio de Optimalidad, dice: “Una política óptima sólo puede estar formado por subpolíticas óptimas”.
Dada la siguiente red:
Programación Dinámica
![Page 14: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/14.jpg)
14
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Si queremos determinar un camino de A a N, este se denominará una política:
![Page 15: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/15.jpg)
15
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Así por ejemplo ADFKMN es una política:
![Page 16: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/16.jpg)
16
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Una subpolítica será una porción continua de un camino. De este modo BEIM es una subpolítica:
![Page 17: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/17.jpg)
17
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Si se desea determinar el camino mínimo de A a N, ACEILN es la política óptima que responde a este objetivo:
![Page 18: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/18.jpg)
18
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Ahora, si se desea determinar una subpolítica óptima de C a L, esta será CEIL:
![Page 19: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/19.jpg)
19
CARACTERISTICAS DE LOS PROBLEMAS DE PDEn los problemas de PD se localizan:
Programación Dinámica
ETAPAS O PERIODOS
VARIABLES DE ESTADO
VARIABLES DE DECISION
FUNCION COSTO-BENEFICIO
OBJETIVO
![Page 20: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/20.jpg)
20
ETAPAS O PERIODOSEs cada una de las partes en las que se divide el problema.
Programación Dinámica
![Page 21: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/21.jpg)
21
Programación Dinámica
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
![Page 22: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/22.jpg)
22
VARIABLES DE ESTADOEs la variable que indica la situación en que se encuentra el problema al inicio de cada etapa. Los valores de esta variable forman el llamado DOMINIO DE ESTADO.
Programación Dinámica
![Page 23: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/23.jpg)
23
Programación Dinámica
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
f1(x1) f2(x2) f3(x3) f4(x4) f5(x5) f6(x6)
![Page 24: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/24.jpg)
24
VARIABLES DE DECISIONEs la variable que indica la decisión a tomar en cada etapa. Los valores de esta variable forman el llamado DOMINIO DE CONTROL.
Programación Dinámica
![Page 25: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/25.jpg)
25
Programación Dinámica
f1(x1) f2(x2) f3(x3) f4(x4) f5(x5) f6(x6)
d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5) d(x5, x6)
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
![Page 26: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/26.jpg)
26
FUNCION COSTO-BENEFICIOEs la función que indica el resultado obtenido cuando en una etapa cualquiera se toma una decisión que depende del estado inicial. Esta función también se denomina FORMULA RECURSIVA DE LA PD.
Programación Dinámica
fi(xi) = min [ d(xi , xi+1) + fi+1(xi+1) ]todas las
rutasfactibles( xi , xi+1 )
FORMULA RECURSIVA HACIA ATRAS
![Page 27: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/27.jpg)
27
Otra forma de presentar la función costo-beneficio es:
Programación Dinámica
fi(xi) = min [ d(xi-1 , xi) + fi-1(xi-1) ]todas las
rutasfactibles( xi-1 , xi )
FORMULA RECURSIVA HACIA ADELANTE
![Page 28: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/28.jpg)
28
OBJETIVODetermina la secuencia de decisiones que optimice la función Costo-Beneficio.
Programación Dinámica
A C
E I L
N28
2 34
![Page 29: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/29.jpg)
29
PROCEDIMIENTO DE LA PDPara resolver un problema por medio de la PD se pueden utilizar diferentes procedimientos.
Los que más se utilizan son los de fórmulas recursivas hacia adelante y los de fórmulas recursivas hacia atrás.
La metodología requiere de dos iteraciones.
La primera iteración denominada DESCENDENTE, es la que resuelve cada etapa integrándolas sucesivamente a las siguientes soluciones. Esta iteración es la más laboriosa.
Programación Dinámica
![Page 30: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/30.jpg)
30
La segunda iteración denominada ASCENDENTE, es la que permite construir la secuencia óptima de decisiones. Esta iteración es la más simple.
La metodología descrita puede ser aplicada en diferente forma sobre un mismo problema.
Programación Dinámica
![Page 31: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/31.jpg)
31
EjemploDado el siguiente grafo determinar la ruta más corta del vértice A al vértice Z.
Programación Dinámica
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
![Page 32: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/32.jpg)
32
Programación Dinámica
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 33: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/33.jpg)
33
Programación Dinámica
Fórmula recursiva hacia atrásfi(xi) = min [ d(xi , xi+1) + fi+1(xi+1) ], i = 1, 2, 3, 4
todas lasrutas
factibles( xi , xi+1 )
fn(xn) = 0
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 34: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/34.jpg)
34
Iteración descendente
Programación Dinámica
f5(x5) = f5(Z) = 0
f4(x4) = min [ d(x4 , x5) + f5(x5) ]ETAPA 4
r. f.
f4(H) = min [ d(H , Z) + f5(Z) ]x4 = H
r. f
f4(H) = min [ 4 + 0 ] = 4r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 35: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/35.jpg)
35
Programación Dinámica
f4(I) = min [ d(I , Z) + f5(Z) ]x4 = I
r. f
f4(I) = min [ 3 + 0 ] = 3r. f
f4(J) = min [ d(J , Z) + f5(Z) ]x4 = J
r. f
f4(J) = min [ 5 + 0 ] = 5r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 36: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/36.jpg)
36
Programación Dinámica
f3(x3) = min [ d(x3 , x4) + f4(x4) ]ETAPA 3
r. f.
f3(E) = min [ d(E , H) + f4(H) , d(E , I) + f4(I) ]
x3 = E
r. f
f3(E) = min [ 6 + 4 , 3 + 3 ] = 6r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 37: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/37.jpg)
37
Programación Dinámica
f3(F) = min [d(F, H)+f4(H), d(F, I)+f4(I), d(F, J)+f4(J)]x3 = F
r. f
f3(F) = min [ 7 + 4 , 5 + 3 , 4 + 5 ] = 8r. f
f3(G) = min [ d(G , I) + f4(I) , d(G , J) + f4(J) ]x3 = G
r. f
f3(G) = min [ 7 + 3 , 4 + 5 ] = 9r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 38: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/38.jpg)
38
Programación Dinámica
f2(x2) = min [ d(x2 , x3) + f3(x3) ]ETAPA 2
r. f.
f2(B) = min [ d(B , E) + f3(E) , d(B , F) + f3(F) ]
x2 = B
r. f
f2(B) = min [ 7 + 6 , 6 + 8 ] = 13r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 39: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/39.jpg)
39
Programación Dinámica
f2(C) = min [d(C, E)+f3(E), d(C, F)+f3(F), d(C, G)+f3(G)]x2 = C
r. f
f2(C) = min [ 4 + 6 , 3 + 8 , 3 + 9 ] = 10r. f
f2(D) = min [ d(D , F) + f3(F) , d(D , G) + f3(G) ]x2 = D
r. f
f2(D) = min [ 4 + 8 , 2 + 9 ] = 11r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 40: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/40.jpg)
40
Programación Dinámica
f1(x1) = min [ d(x1 , x2) + f2(x2) ]ETAPA 1
r. f.
f1(A) = min [d(A ,B)+f2(B), d(A,C)+f2(C), d(A,D)+f2(D)]
x1 = A
r. f
f1(A) = min [ 3 + 13 , 5 + 10 , 2 + 11 ] = 13r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 41: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/41.jpg)
41
Programación Dinámica
Iteración ascendenteLa ruta mínima óptima de A a Z, resulta:
La distancia mínima es: 13
2 2 54 J ZGDA
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 42: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/42.jpg)
42
Programación Dinámica
H ir a Z 4 ir a Z 4I ir a Z 3 ir a Z 3J ir a Z 5 ir a Z 5
DISTANCIA MINIMA
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
FORMA TABULARIteración descendente
ETAPA 4
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 43: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/43.jpg)
43
Programación Dinámica
ir a H 6 + 4 = 10ir a I 3 + 3 = 6ir a H 7 + 4 = 11ir a I 5 + 3 = 8ir a J 4 + 5 = 9ir a I 7 + 3 = 10ir a J 4 + 5 = 9
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
DISTANCIA MINIMA
G
ir a I
ir a I
ir a J
6
8
9
E
F
ETAPA 3
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 44: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/44.jpg)
44
Programación Dinámica
ir a E 7 + 6 = 13ir a F 6 + 8 = 14ir a E 4 + 6 = 10ir a F 3 + 8 = 11ir a G 3 + 9 = 12ir a F 4 + 8 = 12ir a G 2 + 9 = 11
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
DISTANCIA MINIMA
B ir a E 13
C ir a E 10
D ir a G 11
ETAPA 2
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 45: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/45.jpg)
45
Programación Dinámica
ir a B 3 + 13 = 16ir a C 5 + 10 = 15ir a D 2 + 11 = 13
DISTANCIA MINIMA
A ir a D 13
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
ETAPA 1
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
![Page 46: PROGRAMACION DINAMICA](https://reader038.vdocumento.com/reader038/viewer/2022110207/55cf8fd7550346703ba065d3/html5/thumbnails/46.jpg)
46
Programación Dinámica
Iteración ascendenteLa ruta mínima óptima de A a Z, resulta:
La distancia mínima es: 13
2 2 54 J ZGDA
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)