En el problema de la estación de servicio , se nos dan ciudades y carreteras entre ellas. Cada camino tiene longitud y cada ciudad define el precio del combustible. Una unidad de carretera cuesta una unidad de combustible. Nuestro objetivo es ir de una fuente a un destino de la manera más barata posible. Nuestro tanque está limitado por algún valor.{ 0 , ... , n - 1 }
Intento entender el algoritmo , así que escribí manualmente los pasos para calcular la solución. Desafortunadamente, me quedé atascado: en algún momento no hay bordes para considerar, no sé por qué, tal vez me estoy perdiendo algo.
Ejemplo:
carretera:
0 ----------- 1 ------------ 2 -------------- 3
(no tiene que ser así de simple, podría ser cualquier gráfico, es decir, podría haber caminos entre 0-> 2, 0-> 3, 1-> 3, etc.)
Fuente: 0, Destino: 3, Tanque: 10 unidades
Precios de combustible: 0 : 10 unidades, 1 : 10 unidades, 2 : 20 unidades, 3 : 12 unidades
Longitudes: 0-> 1 : 9 unidades, 1-> 2 : 1 unidad, 2-> 3 : 7 unidades
Solución óptima: llene 9 unidades a 0 y 8 unidades a 1. El costo total es de 170 unidades (9 * 10 + 8 * 10).
Así que traté de calcularlo como se muestra aquí (párrafo 2.2)
GV[u] is defined as:
GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}
so in my case:
GV[0] = {0}
GV[1] = {0}
GV[2] = {0, 3, 9}
GV[3] = {0}
D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank:
D(t,0) = 0, otherwise:
D(u,g) = min (foreach length[u][v] <= TankCapacity)
{
D(v,0) + (length[u][v] - g) * fuelPrice[u] : if fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]
D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u] : if fuelPrice[v] > fuelPrice[u]
}
so in my case:
D(0,0) = min { D(1,0) + 9*10 } - D(0,0) should contain minimum cost from 0->3
D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :(
D(2,9) = min { ??? - no edges which follows the condition from the reccurence
Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.
To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:
(0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank].
If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7),
so how can it return optimal solutions?
La recurrencia del documento no parece funcionar o, lo que es más probable, hago algo mal.
¿Alguien podría ayudarme con esto?
fuente
Usando la solución @j_random_hacker, necesitamos transformar nuestro gráfico en un gráfico completo y cambiar la condición de la ecuación (4) a:
El gráfico completo debería verse así:
y cálculos finales:
La ruta a través de 0 -> 1 -> 3 [costo total 170 $] es la solución. Eso es lo que esperábamos :-). Si necesitamos una ruta, entonces deberíamos poder transformar esos bordes adicionales de la solución a los bordes dados al principio (no debería ser muy difícil).
Solo me pregunto cómo deberíamos evitar los puntos muertos en esta recurrencia. Por ejemplo, puede haber un punto muerto entre 0 <-> 1, porque c (0) <= c (1) y c (1) <= c (0).
fuente
La idea es obtener el combustible según sea necesario en la tarifa más barata donde sea que obtenga (paradigma de algoritmo codicioso)
Toma algunos ejemplos. en tu ejemplo
Fuente: 0, Destino: 3, Tanque: 10 unidades Precios de combustible: 0: 10 unidades, 1: 10 unidades, 2: 20 unidades, 3: 12 unidades Longitudes: 0-> 1: 9 unidades, 1-> 2: 1 unidad, 2-> 3: 7 unidades
Al principio tengo que viajar 9 unidades, así que necesito llenar mi tanque a 0 con> = 9 unidades (capacidad> = 9). Ahora, puedo ver en 1,2,3 la tasa de combustible es> = tasa de combustible en 0. Como, quiero comprar mi combustible necesario en la tasa más barata Trataré de llenar 9 + 1 + 7 = 17 unidades en ciudad 0 solamente. Pero, la capacidad del tanque puede ser <17, digamos 10. Entonces, llenaré hasta 10. Entonces a 1 me quedan 1 unidades de combustible y tengo que atravesar 8 unidades más, así que a 1 llenaré 7 Unidades más. No puedo llenar a 2 porque la tasa sería más alta. Mi, costo total = 10 * 10 + 7 * 10 = 170.
El codicioso algoritmo sigue la idea mencionada anteriormente. costo de combustible en la ciudad i. distancia entre dos ciudades y . "lleno" es la unidad de combustible con la que se llena el tanque. "capacidad" es la capacidad máxima del tanque.d i j i jCi dij i j
i) lleno = 0
ii) para a , sea la primera ciudad después de manera que (si no existe tal , entonces ). = more_distance_need_to_travel_till_city_ = . Compre combustible de unidad { lleno, capacidad} en la ciudad . full = { full, capacidad}. Establecer .i=0 n−1 l i Ci>Cl l l=n−1 dl l ∑lk=i+1dk,k+1 min dl− i min dl− i=l
fuente