Беллманс заблудился в лесу: проблема - Википедия - Bellmans lost in a forest problem

Нерешенная проблема в математике: Какой оптимальный путь выбрать, потерявшись в лесу? (больше нерешенных задач по математике)

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

Проверенное решение известно только для нескольких форм или классов форм.^[3] Общее решение могло бы быть в форме геометрического алгоритма, который принимает форму леса в качестве входных данных и возвращает оптимальный путь выхода в качестве выходных данных. Хотя реальные приложения не очевидны, проблема попадает в класс задач геометрической оптимизации, включая стратегии поиска, которые имеют практическое значение. Большим стимулом для учебы была связь с Проблема червя Мозера. Она была включена в список из 12 задач, описанных математиком. Скотт В. Уильямс как «задачи на миллион долларов», потому что он считал, что методы, используемые для их решения, будут стоить математике не менее миллиона долларов.^[4]

Рекомендации