Bellman's lost in a forest problem: Difference between revisions
m ce |
→Approaches: Clarifying which shapes have been solved. |
||
(11 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Unsolved geometric problem}} |
|||
{{short description|What is the best path for a lost hiker to follow to escape from a forest of known shape?}} |
|||
{{unsolved|mathematics|What is the optimal path to take when lost in a forest?}} |
{{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]].<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]] | 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}}</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]] | 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}}</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. |
||
⚫ | 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> |
||
⚫ | |||
⚫ | |||
==Approaches== |
|||
Lost-in-Forest problem has been studied from a blind man's perspective by Surajit Dutta, where he explored the problem based on the condition that the end point of the escape path always lies out side the forest. <ref>{{Cite journal | last1 = Dutta | first1 = Surajit| title = When a blind man is lost in a forest | volume = 8 | issue = 1 | year = 2022 | journal = Journal of Research in Applied Mathematics | pages = 10–14| url=http://www.questjournals.org/jram/papers/v8-i1/C08011014.pdf}}</ref> |
|||
⚫ | |||
| 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}}</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. |
|||
There have been several specific answers found for specific instances, but no general solution has yet been established. For a partial solution that uses an algorithmic approach based on close curve magnetization as an example.<ref>{{Cite journal |last=Agama |first=T. |date=2021-05-10 |title=Simple Close Curve Magnetization and Application to Bellman’s Lost in the Forest Problem |url=https://www.svedbergopen.com/files/1636528854_(4)_IJPAMR06012021MTN003_(p_48-54).pdf |journal=International Journal of Pure and Applied Mathematics Research |volume=1 |issue=1 |pages=48 |doi=10.51483/IJPAMR.1.1.2021.48-54 |issn=2789-9160}}</ref> |
|||
==References== |
==References== |
Latest revision as of 15:20, 1 March 2024
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.
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.[3]
Approaches
[edit]A proven solution is only known for a few shapes or classes of shape, such as a square and a circle. Others, such as an equilateral triangle, remain unknown.[4] 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.
References
[edit]- ^ 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" (PDF). American Mathematical Monthly. 11 (8): 645–654. doi:10.2307/4145038. JSTOR 4145038. MR 2091541.
- ^ Williams, S. W. (2000). "Million buck problems" (PDF). National Association of Mathematicians Newsletter. 31 (2): 1–3.
- ^ Ward, John W. (2008). "Exploring the Bellman Forest Problem" (PDF). Retrieved 2020-12-14.