Проблема Беллмана о заблудившемся в лесу
Проблема Беллмана о заблудившихся в лесу — нерешённая задача минимизации в геометрии , созданная в 1955 году американским математиком-прикладником Ричардом Э. Беллманом . [1] Проблема часто формулируется следующим образом: «Путешественник заблудился в лесу, форма и размеры которого ему точно известны. Каков наилучший путь для него, чтобы выбраться из леса?» [2] Обычно предполагается, что путешественник не знает отправной точки или направления, в котором он находится. Наилучшим путём считается тот, который минимизирует наихудшее расстояние, которое нужно пройти, прежде чем достичь опушки леса. Изучались и другие варианты задачи.
Хотя ненадуманные приложения в реальном мире не очевидны, проблема относится к классу задач геометрической оптимизации, включая стратегии поиска, имеющие практическое значение. Более весомой мотивацией для изучения стала связь с задачей Мозера о червяке . Она была включена в список из 12 задач, описанных математиком Скоттом В. Уильямсом как «задачи на миллион долларов», поскольку он считал, что методы, используемые для их решения, будут стоить математике не менее миллиона долларов. [3]
Подходы
Доказанное решение известно только для нескольких форм или классов форм, таких как правильные многоугольники и круг. В частности, все формы, которые могут охватывать ромб 60° с более длинной диагональю, равной диаметру, имеют решение в виде прямой линии. Равносторонний треугольник является единственным правильным многоугольником, который не обладает этим свойством и имеет решение, состоящее из зигзагообразной линии с тремя сегментами одинаковой длины. Решение для многих других форм остается неизвестным. [4] Общее решение будет иметь форму геометрического алгоритма, который принимает форму леса в качестве входных данных и возвращает оптимальный путь эвакуации в качестве выходных данных.
Ссылки
- ^ Беллман, Р. (1956). «Проблема минимизации». Исследовательские проблемы. Бюллетень Американского математического общества . 62 (3): 270. doi : 10.1090/S0002-9904-1956-10021-9 .
- ^ Финч, SR; Ветцель, JE (2004). «Затерянные в лесу» (PDF) . American Mathematical Monthly . 11 (8): 645– 654. doi :10.2307/4145038. JSTOR 4145038. MR 2091541.
- ^ Уильямс, SW (2000). «Проблемы на миллион баксов» (PDF) . Информационный бюллетень Национальной ассоциации математиков . 31 (2): 1– 3.
- ^ Уорд, Джон В. (2008). «Изучение проблемы леса Беллмана» (PDF) . Получено 14 декабря 2020 г.
