You wish to drive from point A to point B along a highway. You are told beforeha

Question

You wish to drive from point A to point B along a highway. You are told beforehand the capacity C of you gas tank in gallons, your rate F of fuel consumption in gallons/mile, and the rate r in gallons/minute at which you can fill your tank at a gas station. So if you stop to fill your tank from 2 gallons to 8 gallons, you would have to stop for 6/r minutes. And the locations of the gas stations are at x_1, x_2, ..., x_n, where A = x_1 and B = x_n. What's an efficient algorithm for minimizing the time that your are stopped for gas?

Explanation / Answer

GREEDY(I) = [$g_{0}, ldots, g_{n}$], where each value represents time spent at each fillup. OPT(I) = [$o_{0}, ldots, o_{n}$].\ \ Proof: Assume $exists$ input I $ i$ GREEDY(I) $lessthan$ OPT(I)\ At each step in induction: Add the difference between greedy and optimal to the next element, and change the element in optimal to match Greedy. \ Given G(I) = [5,6,7] and \ O(I) = [7,5,6]\ \ $O^{prime}$(I) = [5,7,6], the total remains the same: $OPT^{prime} geq OPT$ and driver is guaranteed to reach the next fillup station.\ $O^{primeprime}$(I) = [5,6,7], $OPT^{primeprime} geq OPT^{prime}$\ Iterate to $OPT leq OPT^{prime} leq OPT^{primeprime} leq ldots = GREEDY$\ Therefore, GREEDY is optimal. $ot$ \ item[(b)] Stop if and only if you don’t have enough gas to make it to the next gas station, and if you stop, fill the tank up all the way. %answer here \ \ Let $r$ = 1, $C$ = 10, $F$ = 1\ Consider three stops at positions 0, 5, and 11\ GREEDY: will expend 10 minutes at stop 1 and 5 minutes at stop 2 for a total of 15 minutes.\ OPT: will expend 5 minutes at stop 1 and 6 minutes at stop 2 for a total of 11 minutes.\ Therefore, GREEDY is not optimal. \ end{enumerate} For each algorithm either prove or disprove that this algorithm correctly solves the problem. Your proof of correctness must use an exchange argument. end{document}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.