Greedy Algorithms. You wish to drive from point A to point B along a highway. Yo
ID: 3772839 • Letter: G
Question
Greedy Algorithms. You wish to drive from point A to point B along a highway. You are told beforehand the capacity C of 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
Solution for given problem is:
Step 1:
Stop at every gas station, and fill the tank with just enough gas to make it to the next gas station.
GREEDY(I) = x1, x2...xn, where each value represents time spent at each fillup.
OPT(I) = O1, O2...On
Step 2:
Proof: Assume exists input I is 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^{prime}(I) = [5,6,7], OPT^{prime} geq OPT{prime}
Iterate to OPT leq OPT^{prime} leq OPT^{primeprime} leq ldots = GREEDY
Therefore, GREEDY is optimal. bot
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
Step 3:
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.