Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.