Suppose that you want to drive across the country along a specific route. You kn
ID: 3687085 • Letter: S
Question
Suppose that you want to drive across the country along a specific route. You know the exact distance between gas stations along your route, and you know how far your car can go on a full tank of gas. Your goal is to stop at as few gas stations as possible.
a) Give a greedy algorithm for deciding where to stop for gas.
b) Suppose that there is an optimal solution S that does not involve making the first stop for gas at the greedy choice. Explain how to transform S into a different optimal solution that does involve making the first stop for gas at the greedy choice.
Explanation / Answer
a)Give a greedy algorithm for deciding where to stop for gas.
The following greedy approach works: Start your trip with a full tank. Check your map to determine the farthest away gas station in your route within n miles. Stop at that gas station, fill up your tank and check your map again to determine the farthest away gas station in your route within n miles from this stop. Repeat the process until you get to final place.
b)Suppose that there is an optimal solution S that does not involve making the first stop for gas at the greedy choice. Explain how to transform S into a different optimal solution that does involve making the first stop for gas at the greedy choice.
Note that our greedy method selected as the first stop the gas station farthest away from your starting point in your route but within n miles from starting point. No optimal method could have selected a farther away gas station since by doing so your car would run out of gas. Hence, any other optimal method would have selected either the same gas station or another one closer to starting point. In both cases, our greedy approach is doing no worse than any other optimal one. We can repeat the same argument for any subsequent stop. Hence, our greedy method cannot do worse than (i.e., stay behind) any optimal method and so our greedy method is optimal.