I came across a bridge crossing problem. It got me wondering: Can it be reduced to some sort of scheduling problem. If not, is there any other general problem it can be reduced to?

Here is the problem:

John, Paul, George and Ringo are standing at one end of a bridge crossing. All four must get to the other side. Each can cross in 1, 2, 5 and 10 minutes respectively. There are the following constraints:

  1. The bridge is rickety and can hold a maximum of two people at once.
  2. There is exactly one torch.
  3. It is dark and too dangerous to cross without a torch.
  4. The crossing is too long for the torch to be thrown across.
  5. When two cross, they go at the speed of the slowest.

Task: Minimise the length of time spent for all four to cross.

  • $\begingroup$ You can phrase this as a shortest path problem. $\endgroup$ – Yuval Filmus Dec 23 '16 at 14:01
  • $\begingroup$ I see that now. Can it be reduced to any simpler problem? $\endgroup$ – justinpc Dec 23 '16 at 14:14
  • $\begingroup$ What could be simpler than shortest path? Perhaps you are looking for a more efficient reduction. $\endgroup$ – Yuval Filmus Dec 23 '16 at 14:59
  • $\begingroup$ Yes, I meant a problem for which a more efficient solution exists. $\endgroup$ – justinpc Dec 23 '16 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.