Reputation: 133
Suppose we are going to travel from A to B, during the travel, there are some stations, d_1,...,d_n where d_1=A, d_n=B, we have the choice to add fuel at each station with cost C_i, suppose if we add gas at station d_i, then we can travel a_i more kilometers. I want to find a dynamic programming algorithm to find the minimum cost to travel to B(suppose such a sequence exists).
I try to use D[i] as the minimum cost of traveling to station i from A, but I am in trouble with figuring out the recurrence relationship. i think i may need to keep track of how long we can travel currently. But that will be too complicated...
Upvotes: 2
Views: 2217
Reputation: 23955
We can consider potential optimisations that could prune search space, depending on the data. The possibility of choosing d_1
produces a (cost, distance)
tuple. At d_i
, we generate new tuples by combining cost_i
and distance_i
with previous tuples, keeping all (cost, distance)
tuples, where distance is greater than d_(i+1)
and no tuple has both a higher cost and a lower distance than another. In other words, we don't want to use gas station i
with a previous tuple where
prev1.cost + c_i ≥ prev2.cost
prev1.dist + d_i ≤ prev2.dist
for some (prev1, prev2)
We can see this relationship geometrically as a zero or negative slope between pairs of points.
distance
| b
| f
| c
| e
| a d
|
-----------------cost
c --> e
, c --> d
, and a --> d
having a non-positive slope mean a
and c
are always better choices so we can discard d
and e
. Rather than a convex hull, we are looking for the sequence of strictly increasing distance along the cost dimension. starting from the lowest cost (higher distance breaking ties), noting that there is never a useful point of greater-cost-with-equal-or-lower-distance
.
At each iteration, if we keep the tuples sorted by cost, we can scan low cost to high, starting at the first distance that's equal or greater than d_(i+1)
(discarding any points to the left), discarding any points with greater or equal cost but lower or equal distance.
Upvotes: 1
Reputation: 131
As you said, you maybe need to keep track of how long we can travel currently. You should use D[i][j] as the minimum cost of traveling to station i from A and leaving j kilometers fuel. In this case, recurrence relationship becomes below.
D[i][j] = min( min{ D[i-k][j+(d_i - d_{i-k})] | k<i }, D[i][j-a_i] + C_i );
The first term min{ D[i-k][j+(d_i - d_{i-k})] | k<i }
means moving to i station from i-k station with (d-i - d_{i-k})
kilometers fuel consumption.
k can take the value of from 0 to i-1.
The second term D[i][j-a_i] + C_i
means adding a_i kilometers gas at station d_i with C_i cost consumption.
In addition, you have to be carefully if you allows adding gas more than one times at same station.
Finally, min{ D[n][*] | '*' is any positive value }
becomes answer.
Upvotes: 1