Prove optimality of greedy strategy for fewest number of stops

Question

Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since the distance is quite long you will need to fill up your tank several times. There are $n$ petrol stations along the way, and your goal is to stop at as few petrol stations as possible.

A natural greedy approach would be to make your first stop at the furthest petrol station, $s$, that is reachable from Eindhoven, then fill up your tank, drive again to the furthest reachable petrol station, and so on, until you can reach your destination. Prove or disprove that this is a good greedy choice. In other words, prove or disprove that there is an optimal solution for this problem that includes a stop at petrol station $s$.

Here is my solution. I prove the greedy strategy leads to an optimal solution. Let $OPT$ be the optimum solution, the set of all stations stopped at whose cardinality is minimal, and let $s$ be the first furthest station reachable from Eindhoven. I consider two cases. The first being that $s \in OPT$. In this case we are done. Now I consider the case where $s \notin OPT$. Then, some other station $s'$ was stopped at, sooner than $s$, since $s$ is the furthest station from Eindhoven. Now, stopping at an earlier station does not decrease the minimum number of stops required and so replacing $s'$ with $s$ leads to another solution $OPT^* = \{ OPT \setminus s' \} \cup \{ s \}$ which is no worse, i.e.:

$size(OPT^*) \leq size(OPT)$

Implying that the optimal solution $OPT$ can potentially be improved by using the greedy choice, contradicting the fact that $OPT$ is optimal and so $OPT$ must contain the greedy choice, i.e. $s \in OPT$. This concludes the proof. A proof could have also been obtained using the "greedy stays ahead" method, but I preferred to use the "cut and paste" reasoning.

Now, what could possible alternative approaches be to solving this problem? For example, a solution using the greedy stays ahead approach would be welcome. Also, if there are any errors with the reasoning it would be appreciated if these are pointed out :).

This problem comes from an algorithms course: https://www.win.tue.nl/~kbuchin/teaching/2IL15/

The problem set itself can be found at: https://www.win.tue.nl/~kbuchin/teaching/2IL15/Homework/hw-A1.pdf

The author of the problem set is Kevin Buchin.

Answer 1

As D.W.'s answer points out, there are a few places where the "proof" in the question is not satisfactory. It is not that straightforward to "justify that stopping at an earlier station does not decrease the minimum number of stops" rigorously, even though it might look obvious.

---

A clearer and easier approach is to prove no other solution can get (strictly) ahead of the greedy algorithm.

Assume the destination, the south of France is indeed reachable and at least one stop is needed. (Otherwise, the case is trivial.)

Suppose the greedy itinerary stops at (petrol) station $s_1,s_2,\cdots, s_k$, reaching $s_{k+1}$, the destination. Suppose another itinerary stops at station $t_1$, $t_2$, $\cdots$.

Let us show that $t_i$ is well-defined and $t_i$ is not closer to the destination than $s_i$ for all $i$, $1\le i\le k$.

Let us do induction on $i$.

• The base case $i=1$ is true obviously.
• Suppose the case $i$ is true, i.e., $t_i$ is as least as far away from the destination as $s_i$, where $1\le i<k$. Since we can only reach as far as $s_{i+1}$ starting from $s_i$ with a full tank as dicataed by the greedy nature, the other itinerary can reach at most as far as $s_{i+1}$ starting from $t_i$. That means the other itinerary must make another stop, i.e. $t_{i+1}$. Moreover, $t_{i+1}$ is not closer to the destination than $s_{i+1}$. Our induction is complete.

In particular, letting $i$ be $k$, we know the other itinerary must stop at $k$ stations at least.

Answer 2

I don't consider this to be a sufficient proof. There are a number of problems with this proof:

Let OPT be the optimum solution

No, you can't make such a definition, as there could be multiple optimal solutions. You might mean to let OPT be any optimum solution.

In this case we are done.

You need to explain why you are done.

Now, stopping at an earlier station does not decrease the minimum number of stops required

This needs to be justified.

contradicting the fact that OPT is optimal

No, there is not necessarily any contradiction. You could have $size(OPT^*) = size(OPT)$, and both OPT and OPT* could be optimal.

Answer 3

The usual method is: You prove that there is an optimal solution. (If you want to minimise X and find that X = 1 + epsilon for some epsilon, there might be no optimal solution, or a value that you want to maximise might be arbitrarily large.) Usually there is an optimal solution.

Then you assume that you have any optimal solution O, you have a greedy solution G, and if O ≠ G then you show how you can change O to get a different solution O', which is more similar to G, and still optimal. And then you have to show that repeatedly finding optimal solutions closer and closer to the greedy solution will eventually find a greedy solution.

In your case you want to minimise the number of tank stops, which is a non-negative integer. Such a problem always has an optimal solution with 0, 1, 2, 3, ... tank stops.

Start with an optimal solution O and the greedy solution G. If they are the same then G is optimal. Otherwise there is a smallest i such that the i-th stop of the optimal solution $O_i$ is different from the i-th stop of the greedy solution $G_i$. $O_i$ is not later than $G_i$ because the greedy solution and the optimal solution started at $O_{i-1} = G_{i-1}$ and the greedy solution couldn't go further than $G_i$, so neither can the optimal solution. If $O_i$ is before $G_i$ then we change the optimal solution to go to $G_i$ instead. It is possible because the greedy version did, and you are in the same state, so you can proceed your optimal solution. The first difference has been moved, so eventually you will get O = I.

When this doesn't work: If the amount of fuel you can pack into your tank is different per station. If your greedy strategy encounters a gas station that only allows you 20 litres of fuel, then it is quite possible that stopping one station earlier and filling your tank is better. In this case modifying the optimal solution to make it more similar to the greedy one fails.

Answer 4

Here’s a slight change to make “greedy” fail: all the gas stations only take banknotes of 10 euro or higher paid in advance, and only allow to pay for gas that fits in your tank.