Если бы вы могли переименовать динамическое программирование ...

Если бы вы могли переименовать динамическое программирование, как бы вы это назвали?

Автобиография Ричарда Беллмана предполагает, что он выбрал термин «динамическое программирование», чтобы преднамеренно отвлекать.

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

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

(Однако, как указывают Рассел и Норвиг в своем учебнике по искусственному интеллекту, эта история должна быть творческим украшением правды. Беллман впервые использовал фразу «динамическое программирование» в 1952 году , а Чарльз Эрвин Уилсон не стал министром обороны до 1953 года. )

В любом случае, первоначальная мотивация Беллмана предполагает многоступенчатое планирование , но, по крайней мере, для алгоритмических целей я бы предпочел что-то вроде скромной рекурсии снизу вверх , только с меньшим количеством слогов.

Существуют два важных аспекта DP: (1) определение подзадач (т. Е. Создание «таблицы», которая может быть многомерным массивом, индексированным, возможно, целыми числами, вершинами, подмножествами вершин и т. Д.) И (2) рекурсивное решение подзадачи. Я предлагаю «табличную / табличную рекурсию» как имя, которое относится к обоим аспектам.

Мемоизация - довольно распространенный вариант.

Чтобы пойти с разделяй и властвуй , я бы сказал, сращивать и объединять.

Я обычно использую оба слова, склеиваю и объединяю при обучении / объяснении DP; но не используется в явном виде. Иногда я использовал совмещение-разделяй-и-властвуй, чтобы противопоставить две парадигмы.

После моей недавней лекции по динамическому программированию в разработке алгоритмов я попросил студентов предложить новое название для этой техники. В то время как «Тяжелое программирование» меня позабавило, мне хотелось чего-то, что могло бы сделать эту технику более запоминающейся. После обсуждения здесь я могу предложить два имени, одно для нисходящего и одно для восходящего:
Multiway-Divide и Memoized-Conquer (он же Divide ^ M & Conquer ^ M), и
объединить все подзадачи (aka Merge_all)

Эта статья ( paywalled doi ) называет проблемы, которые могут быть атакованы с помощью DP, «разложимыми».

Недавно я обсуждал это с некоторыми коллегами, и после жаркой дискуссии мы пришли к табличному кешированию вызовов .

Я бы посоветовал назвать « Индуктивное программирование» - как нечто вроде мостового перехода от наших времен к старым добрым временам Эйлера, Kepler et al. Или, может быть, даже обратное индуктивное программирование . И да, для меня DP сильно ассоциируется с индукцией, в старом добром смысле этого понятия. Мемоизация, кеширование, таблицы и т. Д. - это всего лишь элементы техники, а не ядро ​​подхода к взлому.

Вероятно, то, что включает в себя слова таблицы и заполнить , как это то, что происходит.

Рекурсивный вид или Рекурсивный горизонт

Я бы назвал это «Вперед рекурсия с памяткой».