Bellman's lost-in-a-forest problem
{{Short description|Unsolved geometric problem}}
{{unsolved|mathematics|What is the optimal path to take when lost in a forest?}}
Bellman's lost-in-a-forest problem is an unsolved minimization problem in geometry, originating in 1955 by the American applied mathematician Richard E. Bellman.{{Cite journal | last1 = Bellman | first1 = R. | authorlink = Richard E. Bellman | title = Minimization problem | volume = 62 | issue = 3 | year = 1956 | journal = Bulletin of the American Mathematical Society | pages = 270 | department = Research problems | doi = 10.1090/S0002-9904-1956-10021-9 | doi-access = free }} The problem is often stated as follows: "A hiker is lost in a forest whose shape and dimensions are precisely known to him. What is the best path for him to follow to escape from the forest?"{{Cite journal | last1 = Finch | first1 = S. R.| last2 = Wetzel | first2 = J. E.| title = Lost in a forest | volume = 11 | year = 2004 | journal = American Mathematical Monthly | issue = 8| pages = 645–654 | mr = 2091541 | doi = 10.2307/4145038 | jstor = 4145038| url=https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Finch645-654.pdf}} It is usually assumed that the hiker does not know the starting point or direction he is facing. The best path is taken to be the one that minimizes the worst-case distance to travel before reaching the edge of the forest. Other variations of the problem have been studied.
Although non-contrived real-world applications are not apparent, the problem falls into a class of geometric optimization problems, including search strategies that are of practical importance. A bigger motivation for study has been the connection to Moser's worm problem. It was included in a list of 12 problems described by the mathematician Scott W. Williams as "million buck problems" because he believed that the techniques involved in their resolution will be worth at least a million dollars to mathematics.{{Cite journal | last1 = Williams | first1 = S. W.| title = Million buck problems | volume = 31 | issue = 2 | year = 2000 | journal = National Association of Mathematicians Newsletter | pages = 1–3 | url = http://www.math.buffalo.edu/~sww/0papers/million.buck.problems.mi.pdf}}
Approaches
A proven solution is only known for a few shapes or classes of shape, such as regular polygons and a circle. In particular, all shapes which can enclose a 60° rhombus with longer diagonal equal to the diameter have a solution of a straight line. The equilateral triangle is the only regular polygon which does not have this property, and has a solution consisting of a zig-zag line with three segments of equal length. The solution for many other shapes remains unknown.{{cite web
| last = Ward | first = John W. | title = Exploring the Bellman Forest Problem | url=http://wardsattic.com/math/BellmanForestProblem/BellmanForestProblem.pdf |date=2008 |access-date=2020-12-14}} A general solution would be in the form of a geometric algorithm which takes the shape of the forest as input and returns the optimal escape path as the output.