Answer:
The GREEDY Algorithm
Explanation:
Based on the situation given in question, the Greedy algorithm shall give the optimal solution to professor
Suppose that the cities are at locations0 =x0< x1< . . . < x
We shall use the induction method to prove that G is the optimal solution valid for numbers less than n
We assume another solution Z which we initially consider to be optimum as well, based on that when Z fills the tank, it fills it to full level
Let us state the values in case of n intervals. Given below, we say that g1 is the first stop and z1 is also the first stop.
This can be written as ;
G=g1, g2, . . . , gk
Z=z1, z2, . . . , zk’
Here k’ <= k and k < n
Let I be an idex where for the first time gi is not equal to zi
Considering t= maxi Zi
Z′=g1, z2, z3, . . . , zk′
Now since z2, z3, . . . , zk′ should be an optimal stopping pattern for the problem otherwise we have chosen Z, with smaller gas filling (not feasible)
Using induction hypothesis we conclude thatg2, . . . , gk is an optimal stopping pattern, which is based on greedy algorithm
