Swirl graph traversal algorithm - minimum number of stops

Question

I am at a dead end for this homework. I think I have the correct answer, but I'm not sure how to prove it. I am also not sure how to approach the proof. Here is the problem:

Professor Gekko always dreamed of skating in North Dakota. He plans to cross the state on US 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, not far from the western border with Montana. A professor can carry two liters of water, and he can ride miles for miles before the water runs out. (Since North Dakota is relatively flat, a professor does not have to worry about drinking water more quickly in the mountains than in flat or downhill areas.) The professor will start at Grand Forks with two full liters of water. His official North Dakota state map shows all places along US 2 where he can replenish his water and the distances between these places.

The goal of professors is to minimize the number of water stops along its route throughout the state. Give an effective method by which he can determine which water he should stop. Prove that your strategy gives you the best solution and gives you lead time.

I think he should choose his stops so that he goes the maximum distance before the water runs out. That is, at each stop, if he continues to walk, he will run out of water until the next stop.

I am not sure how to proceed. I would argue that this was done before, but I'm pretty new to this area of ​​CS and can use some guidelines.

Answer 1

Your algorithm is correct.

Try to prove the following by induction on the number of stops stopped. After going through each water location, no other strategy could make fewer stops, and of those that made the same number of stops, no other strategy could leave you with more water.

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

If you do not drink with this strategy, the result is easy to prove.

If you 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 for the last time (therefore, they do not stop at stops and cannot be ahead in the water, since you just got water), otherwise the other strategy was also to get water (otherwise they will remain in the water until the next stop).

This is enough to fill in the induction proof.

If you are struggling with the concept of what is required for formal proof, and how to do it, see How I make evidence ... I also wrote about my experience using this handout here .

Answer 2

I hope my first attempt is really deleted. This was wrong.

Proof of the sketch: if the greedy failure failed, it must have been optimal to bring the city closer to the starting point (further from the finish line) than the one that greedily chose at some point. Ignore the problem before this choice and look at two subtasks: one, starting with the city chosen by the greedy, and the other, which contains the greedy point in the subtask. To avoid a contradiction, a city starting farther from the finish line should have an optimal solution with fewer moves than an optimal solution starting with a greedy point. Ignore how you achieve this optimal solution for both subtasks, only that it exists. Since the unwanted starting point includes the greedy subtask, it must either have the same optimal hop subpoint or more (prove this statement. This can be done by induction, but I think there is simpler evidence that I'm just too tired think. Perhaps you can just say that this is obvious?). If they were equal, then the greedy worked fine. If they are larger, a contradiction.

Answer 3

The trick with similar questions is to indicate the problem as another problem for which you can prove something.

For example, for this you can create an unweighted graph where stops are nodes, and you have an edge between two nodes if you can move between them without stopping. Then all you have to do is find the shortest path on the chart and there you go. This is normal if the distance between stops is relatively small, otherwise the graph becomes very dense. I suspect there is a better problem to reduce as your path is on a line.