1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. Thank you for citing your sources. $\endgroup$
    – D.W.
    Mar 12 at 7:40

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why is it easier to prove as shown in this answer? A fundamental reason is that all data are immutable during the proof. $\endgroup$
    – John L.
    Mar 14 at 2:18
  • $\begingroup$ Also, (mathematical) induction is the powerful way to deduce rigorously. You may want to use it more often when you are asked to write rigorous proofs. $\endgroup$
    – John L.
    Mar 14 at 2:31
3
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Instead of editing the question I'll try and fix the problems with the proof here in the comments, to see if I understand you correctly. To justify that stopping at an earlier station does not decrease the minimum number of stops I reason as follows. Let the range a car can travel on a full tank of gas be constant. Now, we have two scenarios. We stop either at $s$ or earlier at $s'$. The final stop may be within the range of both stations. It may also be out of range of $s'$, but not of $s$, meaning that it may take one more stop if stopped at $s'$, so stopping at $s$ is optimal, in this case. $\endgroup$
    – prcssngnr
    Mar 12 at 15:18
  • $\begingroup$ Now we consider the case where the final stop is out of range of both $s$ and $s'$. Starting from $s$ we now travel as far as possible to $s^*$ and from $s'$ we to go $s''$. The range a car travels is constant and so the distance $d^*$ from the start location travelled greedily is at least as far as $d''$ travelled optimally. Now the destination may be within range of $s^*$ and $s''$, but it could also just be in range of $s^*$ since $d^* \geq d''$. Again implying that it may take one more stop if not travelling greedily. And so I conclude $size(OPT^*) \leq size(OPT)$. $\endgroup$
    – prcssngnr
    Mar 12 at 15:50
  • $\begingroup$ Which means the greedy strategy is at least as good as the optimal solution, and so it is optimal. $\endgroup$
    – prcssngnr
    Mar 12 at 15:51
  • $\begingroup$ Does this adequately justify that stopping at an earlier station does not decrease the minimum number of stops? I feel I should say that this reasoning feels a lot like greedy stays ahead... $\endgroup$
    – prcssngnr
    Mar 12 at 15:53
  • $\begingroup$ @prcssngnr Justification is in the eyes of a beholder. It looks you have convinced yourself that the greedy algorithm is optimal. However, is it convincing for everyone? You assume that "the range a car can travel on a full tank of gas be constant", which is probably not true. That assumption reduces the creditability of your "proof", although it helps explaining the situation. $\endgroup$
    – John L.
    Mar 14 at 2:43
2
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.