Problema de la diligencia

El problema de la diligencia
Un caza fortunas desea ir de Missouri a California en una diligencia, y quiere viajar de la forma más segura posible. Tiene los puntos de salida y destino conocidos,pero tiene múltiples opciones para viajar a través del territorio.
Se entera de la posibilidad de adquirir un seguro de vida como pasajero de la diligencia.
A
B
C
D
E
F
G
H
I
J
El costode la póliza estándar (cij) se muestra en la tabla siguiente
2 | 4 | 3 |
7 | 4 | 6 |
3 | 2 | 4 |
4 | 1 | 5 |
1 | 4 |
6 | 3 |
3 | 3 |
3 |
4 |
J
I
H
F
H I
E
G
D
CB
E F G
A

• Observación: Escoger siempre el arco más barato no es necesariamente
Lo m A B F I J
A DF ?
H
I
• ¿Como modelar el problema con las metodólogas ya vistas?
F
J
• Si estamos en H la decisión es obvia (y única)
• Si estamos en F:cF,H + cH,J o cF,I + cI,J
• O bien:
cF,H + costo ´optimo de H a J o cF,I + costo ´optimo de I a J
• En el problema hay 4 decisiones quetomar para las etapas: 1, 2, 3 ,4
• En cada etapa estaremos en un estado posible y deberemos tomar una decisión
• Sea:
Vn(s) = el costo mínimo para las etapas n, n + 1, . . . , Nsi en la etapa n estamos en el estado s

• Supongamos que d representa el siguiente destino escogido.
• Sea c(s, d) el costo asociado al arco s ! d.
• Entonces:vn(s) = min c(s, d) + vn+1(d)d factibles
• Esta es la recursión básica de programación dinámica.
• Se resuelve de atrás hacia adelante. Condición de borde: v5(J) =...