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

Извините заранее, если этот вопрос звучит глупо ...

Насколько я знаю, построение алгоритма с использованием динамического программирования работает следующим образом:

1. выразить проблему как рекуррентное отношение;
2. Реализуйте рекуррентную связь либо через памятку, либо через восходящий подход.

Насколько я знаю, я сказал все о динамическом программировании. Я имею в виду: динамическое программирование не дает инструментов / правил / методов / теорем для выражения рекуррентных отношений или для превращения их в код.

Итак, что особенного в динамическом программировании? Что это дает вам, кроме расплывчатого метода решения определенных проблем?

Динамическое программирование дает вам возможность подумать о разработке алгоритма. Это часто очень полезно.

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

Динамическое программирование дает вам структурированный способ думать о времени выполнения вашего алгоритма. Время выполнения в основном определяется двумя числами: количеством подзадач, которые вы должны решить, и временем, которое требуется для решения каждой подзадачи. Это обеспечивает удобный и простой способ думать о проблеме разработки алгоритма. Когда у вас есть рекуррентное отношение кандидата, вы можете посмотреть на него и очень быстро понять, каким может быть время выполнения (например, вы часто можете очень быстро определить, сколько будет подзадач, что является нижней границей для время выполнения: если вы решаете экспоненциально много подзадач, то повторение, вероятно, не будет хорошим подходом). Это также поможет вам исключить возможные декомпозиции подзадач. Например, если у нас есть строкаS [ 1 .. i ] S [ j . , n ] S [ i . , j ] n S $S[1..n]$определение подзадачи с помощью префикса или суффикса или подстроки может быть разумным (количество подзадач является полиномиальным по ), но определение подзадачи по подпоследовательности вряд ли будет хорошим подходом (число подзадач экспоненциально по ). Это позволяет вам обрезать «пространство поиска» возможных повторений.$S[1..i]$$S[j..n]$$S[i..j]$$n$$S$$n$

Динамическое программирование дает вам структурированный подход для поиска возможных рекуррентных отношений. Эмпирически этот подход часто эффективен. В частности, есть некоторые эвристические / общие шаблоны, которые вы можете распознать для общих способов определения подзадач в зависимости от типа ввода. Например:

• Если входные данные являются положительным целым числом , один из возможных способов определения подзадачи состоит в замене меньшим целым числом (st ).п п ' 0 ≤ N ' ≤ $n$$n$$n'$$0 \le n' \le n$

• Если входные данные представляют собой строку , некоторые возможные способы определения подзадачи включают: заменить префиксом ; заменить суффиксом ; замените подстрокой . (Здесь подзадача определяется выбором .)S [ 1 .. n ] S [ 1 .. i ] S [ 1 .. n ] S [ j . , n ] S [ 1 .. n ] S [ i . , j ] i , $S[1..n]$$S[1..n]$$S[1..i]$$S[1..n]$$S[j..n]$$S[1..n]$$S[i..j]$$i,j$

• Если вход представляет собой список , сделайте то же самое, что и для строки.

• Если входные данные представляют собой дерево , один из возможных способов определения подзадачи состоит в том, чтобы заменить любым поддеревом (т. Е. Выбрать узел и заменить поддеревом, корнем которого является ; подзадача определяется выбором ).Т Т х Т х $T$$T$$T$$x$$T$$x$$x$

• Если вход представляет собой пару , то рекурсивно посмотрите на тип и тип чтобы определить способ выбора подзадачи для каждого. Другими словами, одним из возможных способов определения подзадачи является замена на где - это подзадача для а - это подзадача для . (Вы также можете рассмотреть подзадачи вида или .)x y ( x , y ) ( x ′ , y ′ ) x ′ x y ′ y ( x , y ′ ) ( x ′ , y $(x,y)$$x$$y$$(x,y)$$(x',y')$$x'$$x$$y'$$y$$(x,y')$$(x',y)$

И так далее. Это дает вам очень полезную эвристику: просто взглянув на сигнатуру метода, вы можете найти список возможных способов определения подзадач. Другими словами, просто взглянув на постановку задачи - рассматривая только типы входных данных - вы можете найти несколько возможных способов определения подзадачи.

Это часто очень полезно. Он не говорит вам, что такое рекуррентное отношение, но когда у вас есть конкретный выбор, как определить подзадачу, часто не так уж сложно разработать соответствующее рекуррентное отношение. Таким образом, он часто превращает разработку алгоритма динамического программирования в структурированный опыт. На бумаге вы записываете список возможных способов определения подзадач (используя эвристику выше). Затем для каждого кандидата вы пытаетесь записать рекуррентное отношение и оцените его время выполнения путем подсчета количества подзадач и времени, затраченного на каждую подзадачу. Испытав каждого кандидата, вы оставляете лучшего, которого смогли найти. Предоставление некоторой структуры процессу разработки алгоритма является основной помощью, так как в противном случае разработка алгоритма может быть пугающей (

Ваше понимание динамического программирования является правильным ( afaik ), и ваш вопрос оправдан.

Я думаю, что дополнительное пространство проектирования, которое мы получаем из вида рецидивов, которые мы называем «динамическим программированием», лучше всего видно по сравнению с другими схемами рекурсивных подходов.

Давайте представим, что наши входные данные - это массивы чтобы выделить понятия.$A[1..n]$

1. Индуктивный подход

   Здесь идея состоит в том, чтобы уменьшить вашу проблему, решить меньшую версию и найти решение для оригинальной. Схематически

   $\qquad f(A) = g\bigl( f(A[1..n-c]), A \bigr)$

   с функция / алгоритм, который переводит решение.$g$

   Пример: поиск суперзвезд за линейное время

2. Разделяй и властвуй

   Разделите входные данные на несколько более мелких частей, решите проблему для каждой и объедините. Схематично (на две части),

   $\qquad f(A) = g\bigl(f(A[1..c]), f(A[c+1..n]), A\bigr)$ .

   Примеры: Merge- / Quicksort, Наименьшее попарное расстояние на плоскости

3. Динамическое программирование

   Рассмотрите все способы разделения проблемы на более мелкие проблемы и выберите лучший. Схематично (на две части),

   $\qquad f(A) = \operatorname{best} \Bigl\{ g\bigl(f(A[1..c]), f(A[c+1..n])\bigr) \Bigm| 1 \leq c \leq n-1 \Bigr\}$ .

   Примеры: Редактировать расстояние, Проблема изменения

   Важное примечание: динамическое программирование - это не грубая сила ! Применение на каждом этапе значительно сокращает пространство поиска.$\operatorname{best}$

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

Урок изучения динамического программирования является то , что это нормально , чтобы попробовать все возможные разбиения (ну, это необходимо для корректности) , потому что он все еще может быть эффективным использованием запоминания.

Динамическое программирование позволяет вам обменять память на время вычислений. Рассмотрим классический пример Фибоначчи.

Фибоначчи определяется повторением . Если вы решите использовать эту рекурсию, вы в конечном итоге сделаете вызовов , поскольку дерево рекурсии представляет собой двоичное дерево с высотой .$Fib(n)=Fib(n-1)+Fib(n-2)$$O(2^n)$$Fib(\cdot)$$n$

Вместо этого вы хотите вычислить , затем использовать это, чтобы найти , использовать это, чтобы найти и т. Д. Это займет всего время.$Fib(2)$$Fib(3)$$Fib(4)$$O(n)$

DP также предоставляет нам базовые методы для преобразования рекуррентного отношения в восходящее решение, но они относительно просты (и обычно включают использование мерной матрицы или границы такой матрицы, где - это число параметров в рекуррентное соотношение). Это хорошо объясняется в любом тексте о DP.$m$$m$

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

Позвольте мне взять в качестве примера проблему нахождения числа возрастающих подпоследовательностей длины в массиве длины . Полезно разбить множество всех подпоследовательностей на классы эквивалентности так, чтобы две подпоследовательности принадлежали одному и тому же классу, если и только если они имеют одинаковую длину и заканчиваются в одном и том же индексе. Все возможных подпоследовательностей принадлежат ровно одному из классов эквивалентности. Такое разбиение сохраняет достаточно информации, чтобы мы могли определить рекуррентное соотношение для размеров классов. Если дает число подпоследовательностей, которые заканчиваются индексом и имеют длину$k$$A$$n$$2^n$$O(n^2)$$f(i, \ell)$$i$$\ell$тогда имеем:

Это повторение решает проблему во времени .$O(n^2k)$