SUNY Geneseo Department of Computer Science

Trip Planning via Dynamic Programming

Return to List of Lectures

Misc

Hour exam one is Thursday (Feb. 28)

• Material from start of semester through recurrences (graphs, BFS, DFS, divide and conquer, induction, recurrences, master method)
• 4 - 6 short-answer questions
• Full class period
• Open book, notes, computer; closed person

I’m out of town next Thursday (Mar. 7)

• “Class” will be on-line discussion
• Details Tuesday

Questions?

Dynamic Programming Trip Planning Example

You want to drive from home to some remote destination. Car has a G gallon gas tank and gets M miles per gallon; trip is long enough that you’ll need to stop for gas, but you want to minimize how much you pay for gas on the trip. There are gas stations along the route, the ith station charges p_i dollars per gallon of gas, and is at distance d_i miles from your home. You leave home with a full tank of gas, and will need to top up at the destination (distance d_n with price p_n).

• Algorithm as corrected and extended through discussion

        tripPlanning( D, P, n )              // p[i] = price per gallon at station i
            let r[0..n] be a new array       // r[j] = min cost to station j
            let s[0..n] be a new array       // s[j] = stop previous to j
            r[0] = 0
            s[0] = 0
            for j = 1 to n                   // j is station arriving at
                q = ∞
                i = j - 1
                while d[j] - d[i] <= GM && i >= 0        //i is station coming from
                    if p[j]*(d[j]-d[i])/M + r[i] < q
                        q = p[j]*(d[j]-d[i])/M + r[i]
                        s[j] = i
                    i = i - 1
                r[j] = q
            return r[n] and s

Some key steps in turning what we had last class into this

• Cost of stopping at station j
  • If you come from station i, then you have driven d[j] - d[i] miles
  • At M miles per gallon, that means you have used (d[j] - d[i]) / M gallons
  • Which costs you p[j] dollars per gallon to replace, or p[j] * (d[j] - d[i]) / M dollars total
  • Total best-case cost of arriving at station j from station i is therefore the cost of filling up at j plus the best cost for arriving at i, or p[j] * (d[j] - d[i]) / M + r[i]
• Systematic way of deriving dynamic programming algorithms
  • Start with a recurrence relation or recursive function that defines the optimization you’re doing
  • In this case
    • r(0) = 0
    • r(n) = min i | d_n - d_i ≤ GM ^ i ≤ n-1 : p_n(d_n - d_i)/M + r(i) if n > 0
  • The recurrence then translates semi-mechanically into an iterative algorithm
    • Algorithm uses array to store values of the function; array has as many dimensions as the function has parameters
    • Algorithm uses loop(s) to fill in the array
    • Body of loops does the computation from the recursive function
    • May use a supplemental array to record how you achieved the optimal cost in order to reconstruct that process

Next

(After exam)

More dynamic programming—matrix chain multiplication

Section 15.2