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

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

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

Варианты задачи

[править | править код]

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

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

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

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

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

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

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

Примечания

[править | править код]
  1. Bellman, 1956, с. 270.
  2. Finch, Wetzel, 2004, с. 645–654.
  3. Finch, Wetzel, 2004, с. 645-654.
  4. Залгаллер, 1961, с. 191–195.
  5. Isbell, 1957, с. 357-359.
  6. Williams, 2000, с. 1–3.
  7. John W. Ward. Exploring the Bellman Forest Problem (2008). Дата обращения: 14 декабря 2020. Архивировано 21 июня 2021 года.
  8. Dutta, 2022, с. 10–14.
  9. Agama, 2021, с. 48.

Литература

[править | править код]
  • В. А. Залгаллер. Как выйти из леса? (Об одной задаче Беллмана) // Матем. просв.. — 1961. — Т. 6. — С. 191–195.
  • J. R. Isbell. An optimal search pattern // Naval Res. Logist.. — 1957. — Вып. Quart. 4.