Graph traversal algorithm with a twist - minimum number of stops

Question

I am stumped on this homework problem. I think I have the right answer but am unsure how to prove it. I am also unsure of how to approach the proof. Here is the problem:

Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations.

The professor’s goal is to minimize the number of water stops along his route across the state. Give an efficient method by which he can determine which water stops he should make. Prove that your strategy yields an optimal solution, and give its running time.

I think he should choose his stops so that he goes the maximum distance before running out of water. That is, at every stop, if he were to keep going, he would run out of water before the next stop.

I am not sure how to proceed. I would bet that this has been done before, but I am rather new to this field of CS and could use some guidance.

Answer 1

Your algorithm is correct.

Try to prove the following by induction on the number of stops passed. After passing each water location, no other strategy can have made fewer stops, and of those which made the same number of stops, no other strategy can leave you with more water.

At 0 stops all strategies are equal, so it is trivial to prove the statement.

If you don't drink at a stop under this strategy, the result is easy to prove.

If you do drink at a stop, from the fact that the statement was true at the previous stop, you can prove that either the other strategy made more stops last time (hence they are not ahead on stops, and can't be ahead on water since you just got water), or else the other strategy must have likewise just got water also (else they will run out of water before the next stop).

That is enough to fill out the induction proof.

If you're struggling about the concept of what is required for a formal proof, and how to do them, see How I Do Proofs. I also blogged about my experience using that handout here.