Rigorous way to solve the river crossing problem

Question

I encountered this classic brain teaser:

Four people, A, B, C and D need to get across a river. The only way to cross the river is by an old bridge, which holds at most 2 people at a time. Being dark, they can't cross the bridge without a torch, of which they only have one. So each pair can only walk at the speed of the slower person. They need to get all of them across to the other side as quickly as possible. A is the slowest and takes 10 minutes to cross; B takes 5 minutes; C takes 2 minutes; and D takes 1 minute.

After trying different combinations of paths, the paths that seems to give the smallest time seem to be: CD -> C -> AB -> D -> CD or CD -> D -> AB -> C -> CD which both give 17 minutes. All other combinations give times that are higher than 17 minutes.

However, is there a systematic way (more rigorous) way to tackle this problem?

Answer 1

On the Bridge and Torch problem wikipedia page it says:

In the case where there are an arbitrary number of people with arbitrary crossing times, and the capacity of the bridge remains equal to two people, the problem has been completely analyzed by graph-theoretic methods.[4]

The reference is to a 2002 paper by Günter Rote "Crossing the bridge at night". In it he derives the minimal solution:

I will present the solution for an arbitrary number $N\ge2$ of people and arbitrary crossing times $0\le t_1\le t_2\le ...\le t_N$.

Theorem 1. The minimum time to cross the bridge is $$\min\{C_0; C_1; ...; C_{\lfloor{N/2}\rfloor−1}\}$$ with $$C_k=(N−2−k)t_1+(2k+1)t+2+\sum_{i=3}^{N}t_i − \sum_{i=1}^{k}t_{N+1−2i}$$ For example, when $N=6$, this amounts to $$\min\{t_1+t_2+t_3+t_4+t_5+t_6; 3t_1+3t_2+t_3+t_4+t_6; 2t_1+4t_2+t_4+t_6\}$$ The difference between $C_{k−1}$ and $C_k$ is $2t_2−t_1−t_{N−2k+1}$. Thus, the optimal value of $k$ can be determined easily by locating the value $2t_2−t_1$ in the sorted list of $t_i$'s.

As you can see, he basically managed to derive all possible solution times in a particular order, and the smallest of them is easy to find by looking at the difference in successive solution times on the list.