The Fuel Reloading Problem is the problem of traveling in a vehicle from one poi

Question

The Fuel Reloading Problem is the problem of traveling in a vehicle from one point to another, with the goal of minimizing the number of times needed to re-fuel. It is assumed that travel starts at point 0 (the origin) of a number line, and proceeds right to some final point F > 0. The input includes F, a list of stations 0 < s1 < s2 < · · · < sn < F, and a distance d that the vehicle can travel on a full tank of fuel before having to re-fuel. Describe in detail a greedy algorithm for solving this problem; in other words, that finds a minimum number of stations that the vehicle needs to re-fuel at. Assume the vehicle begins with a full tank. Clearly explain the greedy choice that is made at each stage.

Explanation / Answer

Let us take an example

Let us suppose you want to travel from california to texas

The following greedy approach works: Start your trip in california 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 San texas.

The same apporach will be used to solve the problem above.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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