A Combinatorial Solution for Bridge and Torch Problem
- PDF / 487,295 Bytes
- 7 Pages / 439.642 x 666.49 pts Page_size
- 33 Downloads / 209 Views
A Combinatorial Solution for Bridge and Torch Problem Marilena Jianu1
· Mihail Jianu2 · Sever Angel Popescu1
Received: 12 June 2020 / Accepted: 10 August 2020 / © Springer Nature Switzerland AG 2020
Abstract In this note we give a combinatorial solution to the general case of the puzzle known as “bridge and torch problem”. It is about finding the shortest time needed for n people to cross a bridge knowing that at most two persons can walk together on the bridge (at the speed of the slowest) and, because it is dark, a torch is needed for each crossing (and they have only one torch). The puzzle can be seen (and solved) as a discrete optimization problem. Keywords Discrete optimization · Integer programming
1 Introduction The bridge and torch problem is a well known puzzle. Four people have to cross a narrow bridge at night. The bridge can be crossed by at most two people at the same time. Because it is dark, a torch must be used at every crossing and they have only one, which must be walked back and forth (it cannot be thrown). Each person walks at a different speed, and, when two people cross the bridge together, they must walk together at the rate of the slower person’s pace. We suppose that person i takes time ti to cross the bridge alone. Given the times ti for each i = 1, . . . , 4 we have to find the shortest time needed for getting all the people across the bridge. In this form, with concrete values ti , the problem first appeared in 1981. An elementary approach Marilena Jianu
[email protected] Mihail Jianu [email protected] Sever Angel Popescu [email protected] 1
Technical University of Civil Engineering of Bucharest, 020396, Bucharest, Romania
2
St Catherine’s College, University of Oxford, Manor Rd, Oxford, OX1 3UJ, UK
21
Page 2 of 7
SN Operations Research Forum
(2020) 1:21
in a combinatorial context is given in [5]. Erwig in [3] used the problem to illustrate that a modern functional programming language like Haskell is at least as suitable as Prolog for programming search problems. Rote [4] gives an extensive bibliography and provides a method for solving the general case with n people by transforming the problem into a special kind of weighted degree-constrained subgraph problem. Backhouse [1] considered the most general case when not only the number of people and the times ti are input parameters, but also the capacity C of the bridge (C is the maximum number of people that are allowed to walk together on the bridge; C = 2 in the classical problem). In [1] and [2] dynamic-programming and integerprogramming algorithms for solving the “capacity-C torch problem” are created. It is also proved that the worst-case time complexity of the dynamic-programming algorithm is proportional to the square of the number of people. In the present paper we propose a combinatorial solution for the standard capacity case C = 2 and arbitrary number of people, n ≥ 3. The main result of the paper is Theorem 1 which states a closed formula for the minimum time needed for crossing. In order
Data Loading...
