Задача Беллмана о потерявшемся в лесу
Задача Беллмана о потерявшемся в лесу — открытая задача минимизации в геометрии, которую поставил в 1955 году американский математик Ричард Беллман[1]. Проблема часто формулируется следующим образом: «Турист заблудился в лесу, форма которого и размеры известны ему в точности. Каков для него лучший путь для выхода из леса?»[2]. Обычно предполагается, что турист не знает начальной точки или направления, в которое он смотрит. Лучшим путём считается тот, который минимизирует худший случай по расстоянию, которое пройдёт турист, прежде чем выйдет из леса.
Варианты задачи править
Сам Беллман предложил два варианта лучшего пути – в первом варианте минимизируется время выхода из леса, во втором варианте минимизируется ожидаемое время выхода из леса. Предлагались и другие варианты, например, максимизирующие вероятность выхода за определённый период[3]. Беллман рассматривал два варианта задачи
- Лес представляет собой бесконечную полосу между двумя параллельными прямыми. Кратчайший путь для этого случая нашёл Залгаллер в 1961 году[4].
- Лес представляет собой полуплоскость и туристу известно расстояние до границы леса. Минимаксный путь описал Исбелл в 1957[5].
В обоих случаях путь единственен с точностью до конгруэнтности. Мало чего известно об оптимальных путях в этих случаях для других интерпретаций «лучший путь».
Хотя приложения задачи в реальном мире не очевидны, задача попадает в класс задач геометрической оптимизации, включая стратегий поиска, которые имеют практическую важность. Сильная мотивация для изучения связана с проблемой червя Мозера. Задача была включена в список 12 проблем, описанных математиком Скоттом У. Уильямсом как «задачи на миллион баксов», поскольку он верил, что техники, вовлечённые в решение этих задач, принесут миллион долларов математикам[6].
Подходы править
Доказанное решение известно только для нескольких фигур или классов фигур[7]. Общее решение должно принимать вид геометрического алгоритма, который принимает в качестве входного параметра форму леса и возвращает оптимальный путь выхода из леса.
Задачу Беллмана о потерявшемся в лесу Сурайджит Дутта изучал с точки зрения слепого[8].
Несколько ответов было найдено для определённых фигур (в частности, для круга, кругового сектора, правильных многоугольников и прямоугольников), но никакого общего решения не было найдено[9].
Примечания править
- ↑ Bellman, 1956, с. 270.
- ↑ Finch, Wetzel, 2004, с. 645–654.
- ↑ Finch, Wetzel, 2004, с. 645-654.
- ↑ Залгаллер, 1961, с. 191–195.
- ↑ Isbell, 1957, с. 357-359.
- ↑ Williams, 2000, с. 1–3.
- ↑ John W. Ward. Exploring the Bellman Forest Problem (2008). Дата обращения: 14 декабря 2020. Архивировано 21 июня 2021 года.
- ↑ Dutta, 2022, с. 10–14.
- ↑ Agama, 2021, с. 48.
Литература править
- В. А. Залгаллер. Как выйти из леса? (Об одной задаче Беллмана) // Матем. просв.. — 1961. — Т. 6. — С. 191–195.
- J. R. Isbell. An optimal search pattern // Naval Res. Logist.. — 1957. — Вып. Quart. 4.
- Richard E. Bellman. Minimization problem // Bulletin of the American Mathematical Society. — 1956. — Т. 62, вып. 3. — doi:10.1090/S0002-9904-1956-10021-9.
- Finch S. R., Wetzel J. E. Lost in a forest // American Mathematical Monthly. — 2004. — Т. 11, вып. 8. — doi:10.2307/4145038. — .
- Williams S. W. Million buck problems // National Association of Mathematicians Newsletter. — 2000. — Т. 31, вып. 2.
- Dutta Surajit. When a blind man is lost in a forest // Journal of Research in Applied Mathematics. — 2022. — Т. 8, вып. 1.
- Agama T. Simple Close Curve Magnetization and Application to Bellman's Lost in the Forest Problem // International Journal of Pure and Applied Mathematics Research. — 2021. — Май (т. 1, вып. 1). — ISSN 2789-9160. — doi:10.51483/IJPAMR.1.1.2021.48-54.