El problema de Bellman perdido en el bosque

El problema de Bellman de perderse en un bosque es un problema de minimización sin resolver en geometría , originado en 1955 por el matemático aplicado estadounidense Richard E. Bellman . ^{[ 2 ]} El problema se suele plantear 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 debe seguir para escapar del bosque?» ^{[ 1 ]} Generalmente se supone que el excursionista desconoce el punto de partida o la dirección en la que se encuentra. Se considera que el mejor camino es aquel que minimiza la distancia máxima a recorrer antes de llegar al borde del bosque. Se han estudiado otras variaciones del problema.

Aunque no se aprecian aplicaciones prácticas no artificiales, el problema pertenece a la clase de problemas de optimización geométrica, incluidas estrategias de búsqueda de importancia práctica. Una motivación aún mayor para su estudio ha sido su conexión con el problema del gusano de Moser . Este problema se incluyó en una lista de 12 problemas descritos por el matemático Scott W. Williams como «problemas del millón de dólares», pues creía que las técnicas implicadas en su resolución aportarían al menos un millón de dólares a las matemáticas. ^{[ 3 ]}

Aunque no se sabe cómo encontrar una solución óptima para una forma arbitraria, se conoce la solución óptima para algunas formas especiales y clases especiales de formas:

• Si el bosque contiene un rombo de 60° cuya diagonal mayor es un diámetro del bosque, entonces la longitud óptima de la ruta de escape es el diámetro, y caminar en línea recta durante esta distancia proporcionará una huida óptima. Este caso incluye, por ejemplo, un bosque circular. ^{[ 1 ]}
• La ruta de escape óptima para un bosque semicircular, o más generalmente un bosque con forma de sector circular con un ángulo de al menos 60°, es también el diámetro del bosque, al igual que la ruta de escape óptima para un polígono regular con más de tres lados. ^{[ 1 ]}
• La ruta de escape óptima para una franja infinita de ancho${\displaystyle w}$es un camino en forma de V formado por cuatro segmentos de línea recta y dos arcos circulares poco profundos, de longitud aproximada${\displaystyle 2.2783w}$. Este mismo camino también es óptimo para rectángulos de altura${\displaystyle w}$cuyo diámetro es mayor o igual que la longitud de este camino. Para rectángulos con un diámetro menor, la longitud óptima del camino de escape es el diámetro. Un rectángulo cuyo diámetro es igual a la longitud del camino de escape para una tira de la misma altura proporciona un ejemplo de una forma con dos caminos de escape óptimos muy diferentes: el camino para la tira y un único segmento de línea de la misma longitud que el diámetro. ^{[ 1 ]}