Algorithmic Problem Solving

In this chapter, we present a solution to a more general version of the problem in Section 3.5. The generalisation is to consider an arbitrary number of people; the task is to get all the people across a bridge in the optimal time. Specifically, the problem we discuss is the following:

N people wish to cross a bridge. It is dark, and it is necessary to use a torch when crossing the bridge, but they only have one torch between them. The bridge is narrow and at most 2 people can be on it at any one time. The people are numbered from 1 thru N. Person i takes time t.i to cross the bridge; when two cross together they must proceed at the speed of the slowest.

Construct an algorithm that will get all N people across in the shortest time.

For simplicity, we assume that t.i < t.j whenever i < j. (This means that we assume the people are ordered according to crossing time and that their crossing times are distinct. Assuming that the crossing times are distinct makes the arguments simpler, but is not essential. If the given times are such that t.i = t.j for some i and j, where i < j, we can always consider pairs (t.i, i), where i ranges over people, ordered lexicographically. Renaming the crossing “times” to be such pairs, we obtain a total ordering on times with the desired property.)

10.1 LOWER AND UPPER BOUNDS

The derivation that follows is quite long and surprisingly difficult, particularly ...