Задача Беллмана о потерявшемся в лесу
Задача Беллмана о потерявшемся в лесу — открытая задача минимизации в геометрии, которую поставил в 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.