CSE 5311 Fall 1999

**Quiz #5**

- 1.
- Professor Midas drives an automobile between two cities
*m*miles apart along an interstate highway. His car can go*n*miles on a tank of gas, and he starts with a full tank. His map indicates that there are*g*gas stations along the way, and*d*(*s*_{i}) is the distance of station*i*from the previous station*s*_{i-1}. The distance to the first gas station is*d*(*s*_{1}), and for all*i*. The professor wishes to minimize the number of gas stops during the trip.- (a)
- (8 points.)
Prove that this road-trip problem exhibits optimal substructure.
Let the start city be

*s*_{0}, the destination city be*d*, and the optimal solution to the trip by the stops . Let*cost*(*S*,*c*_{1},*c*_{2}) be the cost of a solution*S*for traveling from point*c*_{1}to*c*_{2}. Therefore,*cost*(*S*_{opt},*s*_{0},*d*) =*k*.Define a subproblem of the original problem to be the problem of traveling from the first stop

*s*_{a1}in the solution to the destination city*d*. In terms of this subproblem the cost of the optimal solution can be written as

Assume there is a better solution

*S*' to the subproblem of traveling from*s**a*_{1}to*d*, such that

However, if this better solution*S*' exists, then we can use it after our stop at*s*_{a1}to achieve a lower-cost solution to the original problem.

This contradicts the optimality of

*S*_{opt}, and therefore a better solution to the subproblem cannot exist. Thus, the optimal solution to the original problem contains optimal solutions to the subproblems, i.e., the road-trip problem exhibits optimal substructure. - (b)
- (12 points.)
Describe a greedy algorithm for solving the road-trip problem and
prove that your algorithm yields an optimal solution.
The greedy algorithm that leads to an optimal solution is to always go to the farthest stop you can reach on a tank of gas until you reach the destination city.

Since we have already proven optimal substructure for this problem, to show our greedy choice leads to an optimal solution, we need only show that our greedy choice satisfies the greedy choice property, i.e., that the greedy choice is in an optimal solution and can be made first. To show that the greedy choice is in an optimal solution, we will show that an optimal solution not containing the greedy choice can be changed to include the greedy choice without sacrificing optimality (i.e., minimal number of stops).

For the top-level problem of traveling from

*s*_{0}to*d*, let*s*_{g}be the greedy choice for the first stop, and let*s*_{opt}be the first stop specified by an optimal solution. First note that*s*_{opt}must be either the same as or before*s*_{g}. If*s*_{opt}were after*s*_{g}, then the greedy choice would choose*s*_{opt}over*s*_{g}. Also, if*s*_{opt}=*s*_{g}, then we have proven our hypothesis. Lastly, if*s*_{g}is after*s*_{opt}, then we can replace*s*_{opt}by*s*_{g}while maintaining the same minimal number of stops. Thus, the greedy choice is in an optimal solution. Also, since we have shown that the first greedy choice can be the first stop of an optimal solution, the greedy choice can be made first. Optimal substructure completes the inductive proof that our greedy choice leads to an optimal solution.