Dynamic Programming solver for The bridge crossing problem

The bridge crossing problem is here modelled and solved as undiscounted Dynamic Programming problem.

2.5K Downloads

Updated Sat, 01 Nov 2008 18:28:49 +0000

No License

The bridge-crossing problem is a mathematical puzzle where
a group of N persons have to cross a bridge at night. It is dark and they can only cross the bridge if they carry a lamp. Only one lamp is available and at most two persons can cross at the same time. It is not possible to cross from a side if the lamp is not on that side. The time of crossing is the time of the slowest person crossing.

In this simple exercise, the bridge crossing problem is modelled as
undiscounted Dynamic Programming problem with termination state. I know very little about this problem, and I made this script just for fun I guess other approaches exist which are more computationally efficient than this.

Anyway, this one works and can it be used to solve problems up to 10~15 persons in reasonable time.

Cite As

Gianluca Dorini (2023). Dynamic Programming solver for The bridge crossing problem (https://www.mathworks.com/matlabcentral/fileexchange/21969-dynamic-programming-solver-for-the-bridge-crossing-problem), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2007a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.0.0.0