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

43

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

Джек
источник
1
Я бы сказал, что динамическое программирование - это динамическое программирование. Это отдельная концепция от алгоритмов. Если бы вы спросили «алгоритмические приложения динамического программирования», это было бы более логичным для меня.
Ёсио Окамото
1
Конечно, dp - это dp, но программирование и динамика сегодня означают нечто иное, поэтому, когда я преподаю динамическое программирование, я бы хотел, чтобы у него было другое имя.
Джек
4
Извините, я не достаточно ясно Вас интересует динамическое программирование в целом, включая использование в управлении и планировании политики и т. Д., И даже стохастическое динамическое программирование, или просто динамическое программирование как метод проектирования алгоритмов? Основная аудитория здесь будет знать только второе, но ваш вопрос довольно общий, который включает в себя первое.
Ёсио Окамото
1
Ёсио, я думаю, тебе следует объяснить более общую концепцию и различия в ответе, так как это может просветить многих из нас.
Рафаэль
2
Еще одна не совсем насмешливая идея: «вещь, которая дает вам работу в Google» - на основе опыта, накопленного моими студентами :)
Суреш Венкат

Ответы:

50

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

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

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

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

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

Jeffε
источник
10
Конечно, то, что я действительно хотел бы сделать, это переименовать в «Уравнение Беллмана», или, как называют его ученые-компьютерщики, в «любое повторение».
Джефф
2
Ваш ответ был использован здесь: biostar.stackexchange.com/questions/17954
Пьер
28

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

Даниэль Маркс
источник
6
табличная рекурсия имеет приятное чувство.
Суреш Венкат
21

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

Суреш Венкат
источник
8
Мемоизация используется, но не характеризует дп.
Джек,
20
В точку. Мемоизация - это динамическое программирование случайно.
Джефф
@ Профессор Эриксон - очень хорошо сказано. я не могу удержаться от смеха.
Акаш Кумар
7
Тем не менее, если мы выберем новое имя для DP, использование мемоизации будет вполне уместным. Например, «расстояние редактирования может быть вычислено за многократное время с использованием напоминания».
Noam
Динамическое программирование - это особый случай запоминания, плюс явное направление потока управления вместо того, чтобы следовать естественному порядку аппликативной оценки. Жаль, что его обычно учат так, как есть, так как он уделяет слишком много внимания заполнению таблицы, а не рекурсивной спецификации. Это кажется волшебным.
Нил Торонто
8

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

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

V Vinay
источник
6

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

Джек
источник
1
Я не думаю, что создание сильной ассоциации с обычным делом и завоеванием (как в Mergesort) является хорошей идеей. Там подзадачи решаются независимо, и объединяются только два результата. В DP проверенные подзадачи не являются независимыми, и все комбинации проверяются. (оба в грубом выражении). Поэтому я думаю, что имя должно подчеркивать разницу, а не создавать ощущение сходства.
Рафаэль
@ Рафаэль, я разделяю озабоченность опасностями создания прочной ассоциации, но не согласен с твоим утверждением о различиях. В DP очень важно , чтобы подзадачи будут «решать самостоятельно» , даже если решения subsubproblems являются общими. Я обычно отмечаю, что если какой-то оракул скажет вам правильное разделение, это будет разделить и победить, но, поскольку я не говорю по-гречески (в отличие от моего доктора философии), я должен попробовать все возможные варианты.
Джек
2
Да, подзадачи концептуально независимы. Однако я относился к ним, используя те же частичные результаты, как вы указали. Это отделяет DP от D & C, поскольку, например, возможно распараллелить последнее без многократного вычисления подзадач (или передачи результатов) в отличие от первого. Ваша аналогия хороша, но в этом случае не дает названия, так как поиск правильных делений является существенной частью проблемы. Я полагаю, что вы могли бы сказать, что DP - это обобщение D & C, основанное на этих рассуждениях.
Рафаэль
@ Рафаэль, извините за педантизм, но поскольку речь идет об обучении, я хочу, чтобы понятие независимости подзадачи было ясным, а просто сказать «концептуально независимым» не совсем точно. При попытке деления производимые вами подзадачи могут не иметь зависимостей. Ваши другие комментарии сосредоточены на шагах алгоритмов DP; Я предпочитаю сосредоточиться сначала на точном определении проблемы, которая будет решена. Мои любимые примеры: минимальная триангуляция веса и минимальная выпуклая декомпозиция простых многоугольников ( cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html )
Джек,
Это нормально быть подвесным. Но рассмотрите дидактический смысл выбора слов: вы говорите студентам, что подзадачи являются независимыми, а затем даете им алгоритм, который не разделяет их вычисления, но на самом деле в значительной степени опирается на «чередующиеся» вычисления. Я думаю, что это может быть очень запутанным. Следовательно, в какой-то момент вам действительно необходимо разделить концептуальную / математическую / оптимизационную / ... и вычислительную независимость.
Рафаэль
2

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

Кевин Вортман
источник
3
это звучит как то, что вы делаете в аутсорсинговом колл-центре;)
Suresh Venkat
2

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

оборота trg787
источник
моя главная проблема с DP - P., поэтому я не фанат этой идеи ..
Suresh Venkat
1

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

Рафаэль
источник
7
Ба. Динамическое программирование не о таблицах ; речь идет об умной рекурсии.
Джефф
3
Я чувствую, что лучше отделить два аспекта: «Извлечение рекурсивной структуры из проблемы и запись в виде повторения» (моделирование) и «Решение полученного повторения снизу вверх» (алгоритмы). Я чувствую, что динамическое программирование (в алгоритмах) относится к обоим, и это также относится к линейному программированию, целочисленному программированию, полуопределенному программированию и т. Д.
Йошио Окамото
1
Таблицы иногда используются. Динамическое программирование на деревьях (например: максимальное независимое множество) обычно не использует таблицу [= массив] для запоминания повторения; он использует дерево, или, в некоторых случаях, дерево массивов, или массив деревьев, или, в некоторых случаях, декартово произведение деревьев. Аналогично для динамического программирования через Дагса или динамического программирования для древовидных разложений для графов ограниченной ширины дерева.
Джефф
1
Джефф, название техники вряд ли когда-либо охватывает все приложения. Возьмите, например, диагонализацию; в продвинутых приложениях нигде не видно диагонали (или, по крайней мере, не исключительной области действия). Но я все равно не слишком люблю «заполнение стола», хотя думаю, что это может быть разумным названием для начинающих.
Рафаэль
3
Мои 2 цента на эту тему. Динамическое программирование имеет два различных аспекта при разработке алгоритмов. Во-первых, нужно понять механику dp как: умная рекурсия плюс запоминание, приводящее к более быстрому алгоритму. Второй аспект заключается в том, как распознать, что проблема может допустить умную рекурсию и придумать ее. Оба важны для обучения. Что касается последнего, то частым случаем является «разделяй и властвуй» с ограниченным взаимодействием, и, на мой взгляд, стоит особо выделить.
Чандра Чекури,
1

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

отметка
источник
Ленивый горизонт? Вы откладываете расчет большого количества результатов, пока они не понадобятся. DP не должен быть рекурсивным.
Чад Brewbaker
0

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

Вениамин
источник