road:
0 ———– 1 ———— 2 ————– 3
(it doesn’t have to be that simple, it could be any graph i.e. there could be roads between 0->2, 0->3, 1->3 etc.) Source: 0, Destination: 3, Tank: 10 units
Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units
Lengths: 0->1: 9 units, 1->2: 1 unit, 2->3: 7 units
Optimal solution: fill 9 units at 0 and 8 units at 1. Total cost then is 170 units (9 * 10 + 8 * 10). So I tried to calculate it as shown here (paragraph 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?
Recurrence from the document doesn’t seem to work or what’s more likely I do something wrong. Could anybody help me with this?
Asked By : Wojciech Kulik
Answered By : j_random_hacker
c(v) <= c(u) and g < d[u][v]
but it should be
(c(v) <= c(u) or v = t) and g < d[u][v]
to force arrival at t to have no gas left. (Just as with my explanation below for the bug in Fill-Row(u, q), we are never interested in the cost of gas at t. And as with there, another way to fix the problem would be to overwrite c(t) with 0 at the start of the algorithm.) Fixing this mistake (in the published algorithm), combined with adding in the missing edges as I describe below (your mistake :-P), should be enough to get everything working. One thing you’re missing is that the graph G must be complete (first sentence of section 2, p. 4) — and if it’s not complete, any missing edges must be added, with the weights found by taking minimum path lengths in the graph. So e.g. in your example graph, there should be (among others) an edge from 1 to 3 with weight 8 (corresponding to the path via 2), so that in fact GV[3] = { 0, 2 }. I’m not sure whether that will completely solve the problem for you, but it should help. Separately, I think there’s a bug in the Fill-Row(u, q) algorithm on p. 6: this algorithm should treat the case q=1 specially, but it doesn’t. I believe it could be fixed by changing
if c(v) <= c(u)
on line 3 to
if c(v) <= c(u) or q = 1
to force any final leg to arrive at the destination empty. (Intuitively, we should always disregard the price of gas at the final destination, t.) Another way around this would be to overwrite c(t) with 0 at the outset.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/25906
