You want to drive from A to B, and you promised to you would stop for coffee oft

Question

You want to drive from A to B, and you promised to you would stop for coffee often – no more than 100 miles between coffee stops. You want to stop for coffee as few times as possible. You are given a route, and an unsorted list of every coffee joint on that route. For each coffee joint you know how many miles it is from A on your route. Come up with the following greedy algorithm to choose your stops: start with a coffee in A; whenever you get coffee you choose the furthest coffee joint that is within 100 miles on your route, that is, the last coffee joint you reach before you hit the 100 mile limit. Drive to that joint, and get some coffee. Keep doing this until you buy coffee within 100 miles of B, at which point you can safely drive into B. (a) Prove that this algorithm produces an optimal schedule, that is, there is no schedule satisfying your 100-mile promise that has fewer coffee stops on your route.

Explanation / Answer

Greedy algorithm:

1. Let coffeeJoints be the list of all coffee joints en-route A to B. Mark all of them as not visited.

2. Let coffeeJointsDistances be the list of distances of all coffee joints from A. This list should be of same size as coffeeJoints.

3. Let coffeeStops be the list (solution) of all coffee stops.

4. Select first coffee joint (at A) from coffeeJoints and add it to coffeeStops. Also mark it as visited.

5. Filter all coffee joints from coffeeJoints within 100 miles (by checking distances in coffeeJointsDistances) from last visited coffee stop. Let coffeeJointsAt100 be the list of all such joints and coffeeJointsAt10Distances be the list of their distance from last visited stop.

6. Sort coffeeJointsAt100 in the ascending orders of their distances in coffeeJointsAt10Distances.

7. Select a coffee joint from sorted coffeeJointsAt100 with furthest distance and add it to coffeeStops. Also mark this coffee joint as visited.

8. Repeat steps 5,6 and 7 till a coffee joint within 100 miles from B is marked as visited.

Correctness of greedy algorithm:

Let x = [x1,...,xn] be the solution generated by the greedy algorithm and y = [y1,...yn] be any feasible solution.

It can be shown that n(x) <= n(y).

For this, we assume that all coffee joints within 100 miles distance from last visited stop are ordered so that dist(i) <= dist(i+1) for all such i. We also know from greedy strategy that there is a k, 0<=k<=n such that xi = 1, i<=k and xi = 0, for i > k.

For induction, consider number p of positions i such that xi != yi.

1. Induction base: We can see that for p = 0, x and y are same. So n(x) <= n(y) holds

2. Induction hypothesis: Now let m be any arbitrary natural number and n(x) <= n(y) whenever p<=m.

3. Induction step: Try to find a least integer j, 1<=j<=n, such that xj != yj. Since p != 0, such a j exists. Also j <= k, as otherwise y is not a feasible solution.

Since xj != yj, and xj=1 -> yj=0.

Set yj = 1. If the resulting y is a feasible solution, let z denote the resulting y.

If the resulting y is not a feasible solution, there must be an l in [k+1, n] for which yl=1. Set yl = 0. Let z denote the resulting y. As dist(j) <= dist(l), z is a feasible solution.

In either case, n(z) <= n(y) and z differs from x in at most p-1 = m positions. From induction hypothesis, it follows that n(x) <= n(z) <=n(y)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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