Bellman's lost in a forest problem: Difference between revisions
Adding short description: "What is the best path for a lost hiker to follow to escape from a forest of known shape?" (Shortdesc helper) |
Add Ward reference |
||
| Line 3: | Line 3: | ||
'''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]].<ref>{{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 }}</ref> 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?"''<ref>{{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]] | pages = 645-654 | mr = 2091541 | doi = 10.2307/4145038}}</ref> 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. |
'''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]].<ref>{{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 }}</ref> 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?"''<ref>{{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]] | pages = 645-654 | mr = 2091541 | doi = 10.2307/4145038}}</ref> 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. |
||
A proven solution is only known for a few shapes or classes of shape.<ref>{{cite web |
|||
| last = Ward | first = John W. | title = Exploring the Bellman Forest Problem | url=http://wardsattic.com/joomla/Download/BellmanForestProblem.pdf |date=2008 |access-date=2020-12-14}}</ref> 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. Although 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.<ref>{{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}}</ref> |
|||
==References== |
==References== |
||
Revision as of 05:48, 14 December 2020
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.[1] 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?"[2] 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.
A proven solution is only known for a few shapes or classes of shape.[3] 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. Although 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.[4]
References
- ^ Bellman, R. (1956). "Minimization problem". Research problems. Bulletin of the American Mathematical Society. 62 (3): 270. doi:10.1090/S0002-9904-1956-10021-9.
- ^ Finch, S. R.; Wetzel, J. E. (2004). "Lost in a forest". American Mathematical Monthly. 11: 645–654. doi:10.2307/4145038. MR 2091541.
- ^ Ward, John W. (2008). "Exploring the Bellman Forest Problem" (PDF). Retrieved 2020-12-14.
- ^ Williams, S. W. (2000). "Million buck problems" (PDF). National Association of Mathematicians Newsletter. 31 (2): 1–3.