Problem 6. (15 marks) A native Australian named Anatjari wishes to cross a deser

Question

Problem 6. (15 marks) A native Australian named Anatjari wishes to cross a desert carrying only one single water bottle. There are n watering holes hi, h2, ..., hn along the way and he has a map that marks 8 all of them. The only places allowing him to refill his bottle are at these watering holes, but he can select which of the watering holes to stop at. He starts from location s with one bottle of water, and he needs to walk di miles from s to watering hole h, for i-1,2,... . Suppose he can walk at most M miles on one bottle of water, and if he only walks

Explanation / Answer

The algorithm that we are following here is Greedy Algorithm.

lets say W_{i} be the i^{th} water hole

let D be the distance vector for all distances between watering holes.D[i] represents
the distance between W_{i} and W_{i+1}

K be the distance he can walk with one bottle water.

Let's start with the first water hole.

Stops represents the set of stops={}

i=1

while(Wi Exists)

Distance=D[i]

     while(Distance<k)

Distance=Distance+D[i+1]

              i=i+1

     Put Wi in Stops if Wi+1   exists

return set of Stops

the above algorithm checks if sum of consecutive distances are less than the value of k.

if the sum of distance exceeds value of k.

we put the current water hole to the set of stops.

Proof of correctness:

Proof of correctness can be achieved by showing the solution is optimal.

let's say distance vector D= {5, 15, 20, 15}

water holes W={W1, W2 , W3 ,W4 ,W5 }

k=25 be the max distance with single bottle.

after execting the above algorithm

step1: distance=5 < 25 i=1

step2: distance=5+15 <25 i=2

step3: distance=20+15 >25 i=3 put W3 in Stops because W4 exists

step4: distance=D[3]=20<25 i=4

step5: distance=20+15>25 i=5 don't put W6 does not exists according algorithm.

In order to walk through the dessert we have to stop at water hole 3 which is optimal solution

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.