Задача Беллмана о потерявшемся в лесу

Нерешённые проблемы математики: Каков оптимальный путь для выхода из леса?

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

Варианты задачиПравить

Сам Беллман предложил два варианта лучшего пути – в первом варианте минимизируется время выхода из леса, во втором варианте минимизируется ожидаемое время выхода из леса. Предлагались и другие варианты, например, максимизирующие вероятность выхода за определённый период. Беллман рассматривал два варианта задачи

1. Лес представляет собой бесконечную полосу между двумя параллельными прямыми. Кратчайший путь для этого случая нашёл Залгаллер в 1961 году.
2. Лес представляет собой полуплоскость и туристу известно расстояние до границы леса. Минимаксный путь описал Исбелл в 1957.

В обоих случаях путь единственен с точностью до конгруэнтности. Мало чего известно об оптимальных путях в этих случаях для других интерпретаций «лучший путь».

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

ПодходыПравить

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

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

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