Minimum cost of travel path using dynamic programming

user_9194960 0
Viewed 1201

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...

dynamic-programming algorithm
2 Answers

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.

user_118340290

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.

user_20347870
Related