People crossing a bridge (a proof for a greedy algorithm)

Question

The problem

Some people are crossing a bridge. Each one takes a different time to pass.

Assume the people are sorted by their passing time increasingly.

These are the conditions of crossing the bridge:

1. only 1 or 2 people can cross the bridge at the same time in the same direction;
2. the speed of the two people crossing is the same as the slower one;
3. it is night and there is only one flashlight;
4. the people passing the bridge must carry the flashlight;
5. the flashlight cannot be thrown over the bridge so it must be carried back to the other end of the bridge.

My greedy solution

The obvious solution seems to be using the fastest guy to take every one to the other end and come back for the rest.

The proof

I tried to prove it like my text book CLRS:

1. Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.

2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.

3. Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem.

I tried something like this:

If we assume the set of all people in the start is $P$ and the set of all people in the destination is $D$ and $O(x)$ is the function that gives the optimum time by getting the set of people and people $p_i$ and $p_j$ are chosen to pass the bridge and $d_k$ is chosen to return the light and $d_k \in D\cup \{p_i , p_j\}$ then:

$$O(P) = Max( t(p_i) , t(p_j) ) + t(d_k) + O(P-\{p_i , p_j\} \cup {d_k})\,,$$

where $t(p_i)$ is the time it takes for person $p_i$ to pass.

Now I have to assume I have an optimal solution $OS$ and show that I can use the greedy choice instead of the choice the $OS$ has made.

I do not know how to proceed further.

Answer 1

The reason you can't prove that the greedy algorithm is correct is because it isn't.

Suppose the people cross the bridge in times 1, 2, 5 and 10 minutes. The greedy solution involves the one-minute person walking backwards and forwards every time and takes 10+1+5+1+2=19 minutes. The optimal solution is 17 minutes (spoiler, since it's a famous puzzle that people might want to try on their own).

1 and 2 cross, 2 returns with the flashlight, then 5 and 10 cross and 1 returns with the flashlight to collect 2: total time 2+2+10+1+2=17 minutes.