Задача Беллмана о потерявшемся в лесу — открытая задача минимизации в геометрии, которую поставил в 1955 году американский математик Ричард Беллман. Проблема часто формулируется следующим образом: «Турист заблудился в лесу, форма которого и размеры известны ему в точности. Каков для него лучший путь для выхода из леса?». Обычно предполагается, что турист не знает начальной точки или направления, в которое он смотрит. Лучшим путём считается тот, который минимизирует худший случай по расстоянию, которое пройдёт турист, прежде чем выйдет из леса.

Варианты задачи Сам Беллман предложил два варианта лучшего пути – в первом варианте минимизируется время выхода из леса, во втором варианте минимизируется ожидаемое время выхода из леса. Предлагались и другие варианты, например, максимизирующие вероятность выхода за определённый период. Беллман рассматривал два варианта задачи Лес представляет собой бесконечную полосу между двумя параллельными прямыми. Кратчайший путь для этого случая нашёл Залгаллер в 1961 году. Лес представляет собой полуплоскость и туристу известно расстояние до границы леса. Минимаксный путь описал Исбелл в 1957. В обоих случаях путь единственен с точностью до конгруэнтности. Мало чего известно об оптимальных путях в этих случаях для других интерпретаций «лучший путь».

Хотя приложения задачи в реальном мире не очевидны, задача попадает в класс задач геометрической оптимизации, включая стратегий поиска, которые имеют практическую важность. Сильная мотивация для изучения связана с проблемой червя Мозера. Задача была включена в список 12 проблем, описанных математиком Скоттом У. Уильямсом как «задачи на миллион баксов», поскольку он верил, что техники, вовлечённые в решение этих задач, принесут миллион долларов математикам.

Подходы Доказанное решение известно только для нескольких фигур или классов фигур. Общее решение должно принимать вид геометрического алгоритма, который принимает в качестве входного параметра форму леса и возвращает оптимальный путь выхода из леса.

Задачу Беллмана о потерявшемся в лесу Сурайджит Дутта изучал с точки зрения слепого.

Несколько ответов было найдено для определённых фигур (в частности, для круга, кругового сектора, правильных многоугольников и прямоугольников), но никакого общего решения не было найдено.

Примечания

Литература

Категория:Метрическая геометрия Категория:Комбинаторная геометрия Категория:Математические головоломки и досуг