The capacity-C torch problem
The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly non-trivial. The case in which there are just four...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/31279/ |
| _version_ | 1848794166636576768 |
|---|---|
| author | Backhouse, Roland Truong, Tan Minh |
| author_facet | Backhouse, Roland Truong, Tan Minh |
| author_sort | Backhouse, Roland |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly non-trivial. The case in which there are just four people and the capacity of the bridge is two is a well-known puzzle, widely publicised on the internet. We consider the general problem where the number of people, their individual crossing times and the capacity of the bridge are all input parameters. We present two methods to determine the shortest total crossing time: the first expresses the problem as an integer-programming problem that can be solved by a standard linear-programming package, and the second expresses the problem as a shortest-path problem in an acyclic directed graph, i.e. a dynamic-programming solution. The complexity of the integer-programming solution is difficult to predict; its main purpose is to act as an independent test of the correctness of the results returned by the second solution method. The dynamic-programming solution has best- and worst-case time complexity proportional to the square of the number of people. An empirical comparison of the efficiency of both methods is also presented. This manuscript has been accepted for publication in Science of Computer Programming. The manuscript has undergone copyediting, typesetting, and review of the resulting proof before being published in its final form. Please note that during the production process errors may have been discovered which could affect the content, and all disclaimers that apply to the journal apply to this manuscript. |
| first_indexed | 2025-11-14T19:11:52Z |
| format | Article |
| id | nottingham-31279 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:11:52Z |
| publishDate | 2015 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-312792020-05-04T17:05:18Z https://eprints.nottingham.ac.uk/31279/ The capacity-C torch problem Backhouse, Roland Truong, Tan Minh The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly non-trivial. The case in which there are just four people and the capacity of the bridge is two is a well-known puzzle, widely publicised on the internet. We consider the general problem where the number of people, their individual crossing times and the capacity of the bridge are all input parameters. We present two methods to determine the shortest total crossing time: the first expresses the problem as an integer-programming problem that can be solved by a standard linear-programming package, and the second expresses the problem as a shortest-path problem in an acyclic directed graph, i.e. a dynamic-programming solution. The complexity of the integer-programming solution is difficult to predict; its main purpose is to act as an independent test of the correctness of the results returned by the second solution method. The dynamic-programming solution has best- and worst-case time complexity proportional to the square of the number of people. An empirical comparison of the efficiency of both methods is also presented. This manuscript has been accepted for publication in Science of Computer Programming. The manuscript has undergone copyediting, typesetting, and review of the resulting proof before being published in its final form. Please note that during the production process errors may have been discovered which could affect the content, and all disclaimers that apply to the journal apply to this manuscript. Elsevier 2015-05-01 Article PeerReviewed Backhouse, Roland and Truong, Tan Minh (2015) The capacity-C torch problem. Science of Computer Programming, 102 . pp. 76-107. ISSN 0167-6423 Algorithmic problem solving; Dynamic programming; Linear programming; Integer programming; Optimisation http://www.sciencedirect.com/science/article/pii/S0167642315000118 doi:10.1016/j.scico.2015.01.003 doi:10.1016/j.scico.2015.01.003 |
| spellingShingle | Algorithmic problem solving; Dynamic programming; Linear programming; Integer programming; Optimisation Backhouse, Roland Truong, Tan Minh The capacity-C torch problem |
| title | The capacity-C torch problem |
| title_full | The capacity-C torch problem |
| title_fullStr | The capacity-C torch problem |
| title_full_unstemmed | The capacity-C torch problem |
| title_short | The capacity-C torch problem |
| title_sort | capacity-c torch problem |
| topic | Algorithmic problem solving; Dynamic programming; Linear programming; Integer programming; Optimisation |
| url | https://eprints.nottingham.ac.uk/31279/ https://eprints.nottingham.ac.uk/31279/ https://eprints.nottingham.ac.uk/31279/ |