Беллманс заблудился в лесу. - Bellmans lost in a forest problem

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

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

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

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

  1. ^ Беллман, Р. (1956). «Проблема минимизации». Проблемы исследования. Бюллетень Американского математического общества. 62 (3): 270. Дои:10.1090 / S0002-9904-1956-10021-9.
  2. ^ Finch, S. R .; Ветцель, Дж. Э. (2004). «Затерянный в лесу» (PDF). Американский математический ежемесячный журнал. 11: 645–654. Дои:10.2307/4145038. МИСТЕР  2091541.
  3. ^ Уорд, Джон В. (2008). «Изучение проблемы леса Беллмана» (PDF). Получено 2020-12-14.
  4. ^ Уильямс, С. В. (2000). «Проблемы на миллион долларов» (PDF). Информационный бюллетень Национальной ассоциации математиков. 31 (2): 1–3.