TOPICS
Search

Lost in a Forest Problem


The lost in a forest problem is the problem of finding the strategy to guarantee reaching the boundary of a given region ("forest") in the shortest distance (i.e., a strategy having the best worst-case performance). For example, one simple strategy would consist of walking in a straight line in a random direction until encountering a boundary. Although this straightforward approach is indeed the best for some simple geometries, other approaches (e.g., walking in a spiral, alternating left and right turns after traveling some fixed distance, etc.) might be optimal for forests with more complicated boundaries.


Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Bellman, R. "Minimization Problem." Bull. Amer. Math. Soc. 62, 270, 1956.Berzsenyi, G. "Lost in a Forest (A Problem Area Initiated by the Late Richard E. Bellman)." Quantum, p. 41, Nov./Dec. 1995.Finch, S. R. "The Logarithmic Spiral Conjecture." Jan. 10, 2005. http://arxiv.org/abs/math.OC/0501133.Finch, S. R. and Shonder, J. A. "Lost at Sea." Nov. 23, 2004. http://arxiv.org/abs/math.OC/0411518.Finch, S. R. Zhu, L.-Y. "Searching for a Shoreline." Jan. 9, 2005. http://arxiv.org/abs/math.OC/0501123.Finch, S. R. and Wetzel, J. E. "Lost in a Forest." Amer. Math. Monthly 111, 645-654, 2004.Shklarsky, D. O.; Chentzov, N. N.; and Yaglom, I. M. Problem 40 in The USSR Olympiad Problem Book, Vol. 2, Part 2. pp. 22-23, 136-137 and 367, 1973. http://www.mathcad.com/library/LibraryContent/puzzles/soln45/scy.pdf.Tóth, G. "Bellman's Problem." Közéiskolai Matematikai Lapok 65, 53-55, 1982. http://www.mathcad.com/library/LibraryContent/puzzles/soln45/gtoth.pdf.

Referenced on Wolfram|Alpha

Lost in a Forest Problem

Cite this as:

Weisstein, Eric W. "Lost in a Forest Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LostinaForestProblem.html

Subject classifications