A General Solution to Bellman's Lost-in-a-forest Problem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910979059613696 |
|---|---|
| author | Deng, Zhipeng |
| author_facet | Deng, Zhipeng |
| contents | We present a general solution and formulation framework to Bellman's lost-in-a-forest problem. The forest boundary is known and may take any shape. The starting point and the orientation are unspecified. We convert the problem into translation and rotation of the forest boundary. This transformation allows us to formulate this problem as a constrained minimization problem. Upon discretization, the problem becomes a variation of the traveling salesman problem or the Hamiltonian path problem. We leverage discrete optimization and derive several nontrivial results consistent with those from previous papers. This method is general, and we also extend the approach to related problems, including Moser's worm problem and the shortest opaque set problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10686 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A General Solution to Bellman's Lost-in-a-forest Problem Deng, Zhipeng Optimization and Control 49K30, 49Q10, 52A40 We present a general solution and formulation framework to Bellman's lost-in-a-forest problem. The forest boundary is known and may take any shape. The starting point and the orientation are unspecified. We convert the problem into translation and rotation of the forest boundary. This transformation allows us to formulate this problem as a constrained minimization problem. Upon discretization, the problem becomes a variation of the traveling salesman problem or the Hamiltonian path problem. We leverage discrete optimization and derive several nontrivial results consistent with those from previous papers. This method is general, and we also extend the approach to related problems, including Moser's worm problem and the shortest opaque set problem. |
| title | A General Solution to Bellman's Lost-in-a-forest Problem |
| topic | Optimization and Control 49K30, 49Q10, 52A40 |
| url | https://arxiv.org/abs/2412.10686 |