Greedy Algorithms. You wish to drive from point A to point B along a highway You

Question

Greedy Algorithms. You wish to drive from point A to point B along a highway You are told beforehand the capacity C of you gas tank m 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_nwhere A = x_1 and B = x_n. What's an effiecient algorithm for minimizing the time that your are stopped for gas

Explanation / Answer

Greedy Solution ->
-> Start your Trip at A with a full Tank, Check the Map to find the farthest away gas Station where you can reach without running out of fuel.
-> This gas Station will be one of the gas Station between A and B, let it be Xk, such you will not able to reach xk+1 without filling your tank. So at this station (Xk) Stop and fill up your tank and check the map again to find the farthest away gas station in the route within C miles from this stop.
-> do this until you reach your destination.

Proof :-
We can proof it using "the greedy algorithm stays ahead" proof method.
Since our approach select the station which is farthest away from your current location in the route such we can reach the farthest away point without running out of fuel. There is no other Optimal Solution that can select a farther away gas station (as compared to our selected gas station) as if we try to do so we would run out of gas. Hence any other method will select the same (as our) gas station or some other gas station closer to our current location. So our greey can not do worse than any other optimal Solution.

So our solution is optimal.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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