Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was considering how to model the following problem mathematically and was wondering what you thought the best way to do it is.

"A takes 1 minute to cross a bridge, B takes 2 minutes, C takes 5 minutes, D takes 10 minutes. They can cross up to two at a time. Each group needs to have a torch (of which there is only one) with them - meaning that the torch needs to be taken back for the next group to cross. How should the trips be organised such that the total time taken for the group to cross is minimised?"

I can only think of a computationally expensive numerical method where one tries each combination of trips in turn (applying appropriate constraints, such as that A needs to be at the beginning in order to travel from the beginning to the end or that the current combination should be abandonned when the total time exceeds the past best time) and records the combination when it performs better than the past best.

Presumably there are more efficient numerical, and/or more effective non-numerical modelling methods that exist to solve the problem?

Thanks in advance for your contribution.

share|cite|improve this question

closed as too broad by Marshmallow, Jon Mark Perry, choco_addicted, MXYMXY, Jonas Apr 7 at 7:04

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

As far as I know, such problems are usually solved using Dynamic Programming or similar tools. Not too sure though. – Inquest Feb 3 '12 at 11:13
Rather than "modelling a real world situation", I'd say you are trying to "solve computationally a mathematical model". – leonbloy Feb 3 '12 at 14:26
You want either a graph traversal or tree traversal algorithm, depending on whether the problem maps onto a tree or a graph (this one maps most naturally onto a graph, because actions are reversible). Tree and graph traversal are similar, but when traversing a graph you need to keep a list of the nodes you've already visited. A widely used and powerful method for choosing which node to visit next is A* search, if you can find a good heuristic. – Chris Taylor Feb 3 '12 at 17:57
An identical problem was given on our first day of Algorithm Design and Analysis. – Old McStopher Mar 27 '13 at 8:04
As leonboy said, modelling a situation is not the same as solving a problem. You model a problem in order to make it analyzable, not to make it efficient. – DanielV Jan 11 '15 at 21:07