¿Cuál es el camino óptimo a seguir cuando se pierde en un bosque?
El problema de la pérdida en un bosque de Bellman es un problema de minimización sin resolver en geometría , que se originó en 1955 por el matemático aplicado estadounidense Richard E. Bellman . [1] El problema se plantea a menudo de la siguiente manera: "Un excursionista se pierde en un bosque cuya forma y dimensiones conoce con precisión. ¿Cuál es el mejor camino que puede seguir para escapar del bosque?" [2] Por lo general, se supone que el excursionista no conoce el punto de partida o la dirección a la que se enfrenta. Se considera que el mejor camino es el que minimiza la distancia en el peor de los casos a recorrer antes de llegar al borde del bosque. Se han estudiado otras variaciones del problema.
Una solución probada solo se conoce para algunas formas o clases de formas. [3] Una solución general sería en forma de un algoritmo geométrico que toma la forma del bosque como entrada y devuelve la ruta de escape óptima como salida. Aunque las aplicaciones del mundo real no son evidentes, el problema cae dentro de una clase de problemas de optimización geométrica que incluyen estrategias de búsqueda que son de importancia práctica. Una mayor motivación para el estudio ha sido la conexión con el problema de los gusanos de Moser . Se incluyó en una lista de 12 problemas descritos por el matemático Scott W. Williams como "problemas de un millón de dólares" porque creía que las técnicas involucradas en su resolución valdrían al menos un millón de dólares para las matemáticas. [4]
Referencias
- ^ Bellman, R. (1956). "Problema de minimización" . Problemas de investigación. Boletín de la American Mathematical Society . 62 (3): 270. doi : 10.1090 / S0002-9904-1956-10021-9 .
- ^ Finch, SR; Wetzel, JE (2004). "Perdido en un bosque" (PDF) . American Mathematical Monthly . 11 : 645–654. doi : 10.2307 / 4145038 . Señor 2091541 .
- ^ Ward, John W. (2008). "Explorando el problema del bosque de Bellman" (PDF) . Consultado el 14 de diciembre de 2020 .
- ^ Williams, SW (2000). "Problemas de millones de dólares" (PDF) . Boletín de la Asociación Nacional de Matemáticos . 31 (2): 1-3.