Проблема Беллмана «затерянный в лесу» — нерешенная проблема минимизации в геометрии , возникшая в 1955 году американским математиком-прикладником Ричардом Э. Беллманом . [1] Проблема часто формулируется следующим образом: «Путешественник заблудился в лесу, форма и размеры которого ему точно известны. Каков наилучший путь для него, чтобы выбраться из леса?» [2] Обычно предполагается, что турист не знает отправной точки или направления, в котором он стоит. Наилучшим путем считается тот, который сводит к минимуму наихудшее расстояние до границы леса. Были изучены и другие варианты проблемы.
Проверенное решение известно только для нескольких форм или классов форм. [3] Общее решение было бы в форме геометрического алгоритма, который принимает форму леса в качестве входных данных и возвращает оптимальный путь эвакуации в качестве выходных данных. Хотя приложения в реальном мире не очевидны, проблема относится к классу задач геометрической оптимизации, включая стратегии поиска, которые имеют практическое значение. Большей мотивацией для изучения была связь с проблемой червя Мозера . Она была включена в список из 12 задач, описанных математиком Скоттом В. Уильямсом как «задачи на миллион долларов», поскольку он считал, что методы, используемые для их решения, принесут математике не менее миллиона долларов. [4]
Проблема «Затерянные в лесу» была изучена с точки зрения слепого Сураджитом Даттой, где он исследовал проблему, исходя из условия, что конечная точка пути побега всегда находится за пределами леса. [5]
Было найдено несколько конкретных ответов для конкретных случаев, но общего решения пока не найдено. Для частичного решения, в котором в качестве примера используется алгоритмический подход, основанный на намагничивании близкой кривой. [6]