Что такое «динамический» в динамическом программировании?

У одного из моих пожилых людей было собеседование, и его спросили, почему это называется динамическим. Он не мог ответить, и после того, как он сдался, интервьюер сказал, что в этом нет ничего динамичного, его просто так называют. В это трудно поверить.

Относится ли это к тому, что подзадачи решаются во время выполнения и используются для достижения конечной цели? Как динамическое распределение памяти, которое происходит во время выполнения?

[ОТВЕТ]

Я должен был прочитать эту статью, прежде чем задавать вопрос, извините.

Я всегда интуитивно понимал, что это означает, что алгоритмы, использующие динамическое программирование, казалось, редактируют проблемное пространство « динамически », пока проблема не может быть решена с помощью жадного алгоритма.

Например, в задаче « Шахматная доска» алгоритм динамического программирования редактирует всю доску по мере ее прохождения, а затем, наконец, можно использовать жадный алгоритм (аналогично алгоритму Дейкстры по кратчайшему пути и т. Д.).

Я не уверен, если это обобщает все проблемы динамического программирования, хотя.

На самом деле, в названии «динамическое программирование» нет ничего особенного; Сама техника - это просто умная раскрутка рекурсии. Посмотрите на этот вопрос и посмотрите на ответ @Jeffe, в котором сообщается, что Бельман выбрал это имя, чтобы преднамеренно отвлекать.

Здесь есть интересная история. Беллман был пионером этой парадигмы. Но это было на самом деле математическое исследование. В свое время, тогдашний министр обороны был параноидален со словами Research and Math (сумасшедший парень, верно!). Беллман испугался, что секретарта разозлит его работа и в итоге он попадет в беду. Поэтому, чтобы немного размыть вещи, он назвал это динамическим программированием , однако в этом нет ничего «динамического».

Ричард Беллман назвал это динамическим программированием в словах Беллмана

Я провел осенний квартал (1950 года) в RAND. Моей первой задачей было найти название для многоступенчатых процессов принятия решений.

Интересный вопрос: откуда появилось название «динамическое программирование»? 1950-е годы не были хорошими годами для математических исследований. У нас был очень интересный джентльмен в Вашингтоне по имени Уилсон. Он был министром обороны, и у него действительно был патологический страх и ненависть к слову «исследование». Я не использую термин слегка; Я использую это точно. Его лицо будет наполнено кровью, он покраснеет и станет жестоким, если люди будут использовать термин «исследование» в его присутствии. Вы можете представить, что он чувствовал тогда по поводу термина «математический». Корпорация RAND была нанята военно-воздушными силами, и, по существу, в качестве начальника ВВС был Вильсон. Поэтому я чувствовал, что должен что-то сделать, чтобы оградить Уилсона и ВВС от того факта, что я действительно занимался математикой в ​​корпорации RAND. Какое название, какое имя, я мог выбрать? Во-первых, меня интересовало планирование, принятие решений, мышление. Но планирование, это не хорошее слово по разным причинам. Поэтому я решил использовать слово «программирование». Я хотел донести мысль о том, что это было динамично, многоступенчато, менялось во времени. Я думал, давайте убьем двух зайцев одним выстрелом. Давайте возьмем слово, которое имеет абсолютно точное значение, а именно динамическое, в классическом физическом смысле. Он также имеет очень интересное свойство в качестве прилагательного, и что слово «динамический» невозможно использовать в уничижительном смысле. Попробуйте подумать о какой-то комбинации, которая, возможно, придаст ей уничижительный смысл. Это невозможно. Таким образом, я думал, что динамическое программирование было хорошим именем. Это было то, на что даже конгрессмен не мог возразить.

Источник: Глаз Урагана, Ричард Беллман (Автобиография)