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.
The optimal strategy is: Greedy solution
The steps are:
We can write optimal substructure of this problem.
Suppose there are n possible refilling locations.
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.
Therefore, he would get at least as far without filling up again if he had chosen the kth location
16.2-4 Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross...
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...