L problema es de una red de viaje donde hay que encontrar un camino para llegar del punto A

Tarea que no calificara :P

[pic 1]

EL problema es de una red de viaje donde hay que encontrar un camino para llegar del punto A (0,0) al punto P (6,0)  con un costo mínimo.

El eje t representa el “tiempo” o “pasos”.  

Cada vez que te muevas de un nodo a otro tendrás que pagar lo que indica el vértice.

Cada vez que damos una “vuelta” , es decir, que subimos en este movimiento [Ejemplo: salimos del Nodo E y llegamos al Nodo H  • (2,0) al (3,1) Subimos en Y] y en el siguiente movimiento bajamos [Ejemplo: nos movimos del Nodo H al Nodo L • (3,1) al (4,0)) ahí bajamos en Y] nos cobraran $2,   aplica cada vez que vamos de arriba hacia abajo o de abajo hacia arriba.

 [pic 2][pic 3][pic 4][pic 5]

Y tendremos 2 (ticket) cupones de “viaje gratis” para usarlo en cualquier momento, es decir si tu quieres aplicar un cupon en del Nodo K al Nodo N no pagaras los 5 que están indicados[pic 6]

Respuesta por Dynamic Programming

[pic 7]

Primero

Denotemos a la función G del punto (t,y) =  donde X es la dirección de donde viene U para arriba, D para abajo, X = { U , D }, Y es la posición de la coordenada Y del punto y Z el número de Tickets de Viaje Gratis.[pic 8][pic 9]

Ejemplo   Esto quiere decir que estamos en el Nodo F, con Y = -2 , que venimos hacia abajo ( X = D) y que tenemos 2 ticket (cupones) disponibles ( Z = 2 ) [pic 10]

Cada vez que estas en un nodo tienes 4 opciones:
ir hacia arriba con o sin cupón
o ir hacia abajo con o sin cupón[pic 11][pic 12][pic 13]

[pic 14]

** AGREGAR EL 2 SI hay vuelta [ U cambia a D o viceversa]!!!

Paso 1 
[pic 15]

Aquí definimos el inicio desde A (0,0) y sus posibilidades de Camino. Y como es el principal X no tiene valor ya que de  ahí partimos.

Paso 2
[pic 16]

[pic 17]

[pic 18]

[pic 19]

**OJO CADA VEZ SERAN MAS OPCIONES YA QUE VARIA LA DIRECCION y LOS CUPONES {2 opciones de dirección[Arribay abajo] y 3 de cupones [ No HAY, queda 1 y quedan 2]) ASI QUE CRECE MUCHO EL PROBLEMA**

Paso 3

[pic 20]

[pic 21]

[pic 22]

[pic 23]

[pic 24]

[pic 25]

[pic 26]

[pic 27]

[pic 28]

[pic 29]

[pic 30]

[pic 31]

**AQUÍ YA ESTA HORRIBLE Y TODAVIA FALTA MAS**

PASO 4

[pic 32]

[pic 33]

[pic 34]

[pic 35]

[pic 36]

[pic 37]

[pic 38]

[pic 39]

[pic 40]

[pic 41]

[pic 42]

[pic 43]

[pic 44]

[pic 45]

[pic 46]

[pic 47]

[pic 48]

[pic 49]

PASO 5

[pic 50]

[pic 51]

[pic 52]

[pic 53]

[pic 54]

[pic 55]

[pic 56]

[pic 57]

[pic 58]

[pic 59]

[pic 60]

[pic 61]

[pic 62]

[pic 63]

[pic 64]

[pic 65]

[pic 66]

[pic 67]

**LOS QUE ESTAN ROJO NO TIENE SENTIDO YA QUE SE BUSCA MINIMAR COSTOS Y ES ILOGICO QUE NO USE TODOS LOS PASES EN EL TRAYECTO**

...