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 ifrom the previous station s_i-1. The distance to the first gas station is d(s₁), and $0 < d(s_i) \leq n$ 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₀, the destination city be d, and the optimal solution to the trip by the stops . Let cost(S,c₁,c₂) be the cost of a solution S for traveling from point c₁ to c₂. Therefore, cost(S_opt,s₀,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

$$cost(S_{opt},s_0,d) = 1 + cost(S_{opt} - \{s_{a_1}\}, s_{a_1}, d).$$

Assume there is a better solution S' to the subproblem of traveling from sa₁ to d, such that

$$cost(S',s_{a_1},d) < cost(S_{opt} - \{s_{a_1}\}, s_{a_1}, d).$$

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.

$$\begin{eqnarray*}cost(\{s_{a_1}\} + S',s_0,d) & = & 1 + cost(S',s_{a_1},d) \\ ... ..._{opt} - \{s_{a_1}\}, s_{a_1}, d) \\ & = & cost(S_{opt},s_0,d) \end{eqnarray*}$$

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₀ 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.