Question

16.2-4 Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross...

16.2-4

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.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

The optimal strategy is: Greedy solution

The steps are:

  • By starting with both bottles full, Professor Gekko should go to the westernmost place that he can refill his bottles within m miles of Grand Forks. Fill up there.
  • Then go to the westernmost refilling location which he can get to within m miles of where he filled up. Fill up there, and so on.
  • Looked at another way, at each refilling location, Professor Gekko should check whether he can make it to the next refilling location without stopping at this one.
    • If he can, skip this one.
    • If he cannot, then fill up.
  • Professor Gekko doesn’t need to know how much water he has or how far the next refilling location is to implement this approach.
    • Because at each fillup, he can determine which is the next location at which he’ll need to stop.

We can write optimal substructure of this problem.

Suppose there are n possible refilling locations.

  • Consider an optimal solution with s refilling locations and whose first stop is at the kth location.
  • Then the rest of the optimal solution must be an optimal solution to the sub problem of the remaining n − k stations.

Otherwise, if there was a better solution to the sub problem, i.e., one with fewer than s−1 stops, we could use it to come up with a solution with fewer than s stops for the full problem, which will contradict our supposition of optimality.

We can also have greedy-choice property for this problem:

Suppose there are k refilling locations beyond the start that are within m miles of the start.

  • The greedy solution chooses the kth location as its first stop.
  • No station beyond the kth works as a first stop.
    • Because Professor Gekko would run out of water first.
    • If a solution chooses a location j < k as its first stop, then Professor Gekko could choose the kthlocation instead, having at least as much water when he leaves the kth location as if he’d chosen the jth location.

Therefore, he would get at least as far without filling up again if he had chosen the kth location

Add a comment
Know the answer?
Add Answer to:
16.2-4 Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • 16.2 #4) Please answer full question thoroughly showing detailed work. SUBMIT ORIGINAL (not book solutions) work and e...

    16.2 #4) Please answer full question thoroughly showing detailed work. SUBMIT ORIGINAL (not book solutions) work and ensure it is correct for thumbs up. If work is NOT ORIGINAL will give THUMBS DOWN!!! 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...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT