dynamic-programming учебник
Начало работы с динамическим программированием

замечания

Введение в динамическое программирование

Динамическое программирование решает проблемы, объединяя решения с подзадачами. Он может быть аналогичен методу деления и покорения, где проблема разбивается на непересекающиеся подзадачи, подзадачи рекурсивно решают и затем объединяются, чтобы найти решение исходной задачи. Напротив, динамическое программирование применяется, когда подзадачи накладываются друг на друга, то есть когда подзадачи имеют общие подзадачи. В этом контексте алгоритм «разделяй и властвуй» работает больше, чем необходимо, многократно решая общие подзадачи. Алгоритм динамического программирования решает каждую подзадачу только один раз, а затем сохраняет свой ответ в таблице, тем самым избегая работы по пересчету ответа каждый раз, когда он решает каждую подзадачу.

Давайте посмотрим на пример. Итальянский математик Леонардо Пизано Биголло , которого мы обычно знаем как Фибоначчи, обнаружил ряд серий, рассматривая идеализированный рост популяции кроликов . Серия:

1, 1, 2, 3, 5, 8, 13, 21, ......

Мы можем заметить, что каждое число после первых двух является суммой двух предыдущих чисел. Теперь давайте сформулируем функцию F (n) , которая вернет нам n-е число Фибоначчи, что означает,

F(n) = nth Fibonacci Number

До сих пор мы это знали,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

Мы можем обобщить его:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Теперь, если мы хотим записать его как рекурсивную функцию, мы имеем F(1) и F(2) качестве базового случая. Таким образом, наша функция Фибоначчи будет:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Теперь, если мы будем называть F(6) , он будет называть F(5) и F(4) , что будет называть еще несколько. Представим это графически:

Из рисунка видно, что F(6) вызовет F(5) и F(4) . Теперь F(5) вызовет F(4) и F(3) . После вычисления F(5) можно с уверенностью сказать, что все функции, которые были вызваны F(5) уже были рассчитаны. Это означает, что мы уже рассчитали F(4) . Но мы снова вычисляем F(4) как указывает правый ребенок F(6) . Нужно ли нам пересчитывать? Мы можем сделать это, как только мы вычислим значение F(4) , мы сохраним его в массиве с именем dp и будем использовать его при необходимости. Мы инициализируем наш массив dp с -1 (или любым значением, которое не будет получено в нашем расчете). Тогда мы будем называть F (6), где наш модифицированный F (n) будет выглядеть так:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Мы выполнили ту же задачу, что и раньше, но с простой оптимизацией. То есть, мы использовали метод memoization . Сначала все значения массива dp будут равны -1 . Когда вызывается F(4) , мы проверяем, пуст он или нет. Если он хранит -1 , мы вычислим его значение и сохраним его в dp [4] . Если он хранит что-либо, кроме -1 , это означает, что мы уже рассчитали его значение. Поэтому мы просто вернем значение.

Эта простая оптимизация с использованием memoization называется динамическим программированием .

Проблема может быть решена с помощью динамического программирования, если она имеет некоторые характеристики. Это:

• подзадач:
  Проблема DP может быть разделена на одну или несколько подзадач. Например: F(4) можно разделить на более мелкие подзадачи F(3) и F(2) . Поскольку подзадачи аналогичны нашей основной проблеме, они могут быть решены с использованием той же техники.
• Перекрывающиеся подзадачи:
  Проблема DP должна иметь перекрывающиеся подзадачи. Это означает, что должна быть какая-то общая часть, для которой одна и та же функция называется более одного раза. Например: F(5) и F(6) имеют F(3) и F(4) . Именно по этой причине мы сохранили значения в нашем массиве.

• Оптимальная структура:
  Допустим, вас попросят свести к минимуму функцию g(x) . Вы знаете, что значение g(x) зависит от g(y) и g(z) . Теперь, если мы можем минимизировать g(x) , минимизируя как g(y) и g(z) , только тогда можно сказать, что задача имеет оптимальную подструктуру. Если g(x) минимизируется минимизацией g(y) и если минимизация или максимизация g(z) не оказывает никакого влияния на g(x) , то эта задача не имеет оптимальной подструктуры. Говоря простыми словами, если оптимальное решение задачи можно найти из оптимального решения ее подзадачи, то можно сказать, что проблема имеет свойство оптимальной субструктуры.

Понимание состояния в динамическом программировании

Давайте обсудим с примером. Из n элементов, сколько способов вы можете выбрать r элементов? Вы знаете, что это обозначается , Теперь подумайте об одном элементе.

• Если вы не выбираете элемент, после этого вам нужно взять r предметов из оставшихся элементов n-1 , которые даются ,
• Если вы выберете элемент, после этого вы должны взять r-1 предметов из оставшихся n-1 предметов, которые даются ,

Суммирование этих двух дает нам общее количество способов. То есть:

Если мы считаем nCr(n,r) как функцию, которая принимает n и r как параметр и определяет , мы можем написать упомянутое выше соотношение как:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

Это рекурсивное отношение. Чтобы его завершить, нам нужно определить базовый регистр (ы). Мы знаем это, а также , Используя эти два в качестве базовых случаев, наш алгоритм определяет будет:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Если мы посмотрим на процедуру графически, мы увидим, что некоторые рекурсии вызываются более одного раза. Например: если взять n = 8 и r = 5 , получим:

Мы можем избежать повторного вызова, используя массив, dp . Поскольку существует 2 параметра, нам понадобится 2D-массив. Мы инициализируем массив dp с -1 , где -1 означает, что значение еще не рассчитано. Наша процедура будет:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Определить , нам потребовались два параметра n и r . Эти параметры называются состояниями . Мы можем просто вывести, что число состояний определяет число измерений массива dp . Размер массива изменится в соответствии с нашей потребностью. Наши алгоритмы динамического программирования будут поддерживать следующую общую схему:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

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

Построение решения DP

Независимо от того, сколько проблем вы решаете с помощью динамического программирования (DP), оно все равно может вас удивить. Но, как и все остальное в жизни, практика делает вас лучше. Помня об этом, мы рассмотрим процесс построения решения для задач DP. Другие примеры на эту тему помогут вам понять, что такое DP и как он работает. В этом примере мы попытаемся понять, как придумать решение DP с нуля.

Итеративный VS Рекурсивный:
Существует два метода построения решения DP. Они есть:

• Итеративный (с использованием циклов)
• Рекурсивный (с использованием рекурсии)

Например, алгоритм вычисления длины самой длинной общей подпоследовательности двух строк s1 и s2 будет выглядеть так:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Это итеративное решение. Существует несколько причин, по которым он закодирован таким образом:

• Итерация выполняется быстрее, чем рекурсия.
• Определение сложности времени и пространства проще.
• Исходный код короткий и чистый

Рассматривая исходный код, вы можете легко понять, как и почему он работает, но трудно понять, как решить это решение. Однако два упомянутых выше подхода переводят на два разных псевдокода. Один использует итерацию (Bottom-Up), а другой использует метод рекурсии (сверху вниз). Последняя известна также как метод memoization. Однако два решения более или менее эквивалентны, и их можно легко преобразовать в другое. В этом примере мы покажем, как найти рекурсивное решение проблемы.

Пример:
Предположим, у вас есть N ( 1, 2, 3, ...., N ) вина, расположенные рядом друг с другом на полке. Цена i- го вина - p [i] . Цена вин увеличивается с каждым годом. Предположим, что это год 1 , в год y цена i- го вина будет: год * цена вина = y * p [i] . Вы хотите продать вина, которые у вас есть, но вы должны продавать ровно одно вино в год, начиная с этого года. Опять же, каждый год вам разрешается продавать только самое левое или самое правое вино, и вы не можете переставить вина, это значит, что они должны оставаться в том же порядке, в каком они были в начале.

Например: допустим, у вас есть 4 вина на полке, и их цены (слева направо):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

Оптимальным решением было бы продать вина в порядке 1 -> 4 -> 3 -> 2 , что даст нам полную прибыль:

Жадный подход:
После мозгового штурма какое-то время вы можете придумать решение о продаже дорогого вина как можно позже. Таким образом, ваша жадная стратегия будет:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Хотя в стратегии не упоминается, что делать, когда две вина стоят одинаково, стратегия вроде бы кажется правильной. Но, к сожалению, это не так. Если цены на вина:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

Жадная стратегия будет продавать их в порядке 1 -> 2 -> 5 -> 4 -> 3 для общей прибыли:

Но мы можем сделать лучше, если мы продадим вина в порядке 1 -> 5 -> 4 -> 2 -> 3 для общей прибыли:

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

Откат:
Чтобы придумать решение для memoization для решения проблемы поиска обратного пути, это удобно. Решение Backtrack оценивает все допустимые ответы на проблему и выбирает лучший. Для большинства проблем легче придумать такое решение. При приближении к решению обратного пути могут быть три стратегии:

1. это должна быть функция, которая вычисляет ответ с помощью рекурсии.
2. он должен вернуть ответ с помощью оператора return .
3. все нелокальные переменные должны использоваться как только для чтения, т. е. функция может изменять только локальные переменные и ее аргументы.

Для нашей примерной проблемы мы попытаемся продать самое левое или самое правое вино и рекурсивно вычислить ответ и вернуть лучший. Решение обратного пути будет выглядеть так:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Если мы будем называть процедуру using profitDetermination(1, 0, n-1) , где n - общее количество вин, оно вернет ответ.

Это решение просто пробует все возможные допустимые комбинации продажи вин. Если в начале есть n вин, он будет проверять возможности. Хотя теперь мы получаем правильный ответ, временная сложность алгоритма растет экспоненциально.

Правильно написанная функция обратного отслеживания всегда должна представлять собой ответ на хорошо сформулированный вопрос. В нашем примере процедура profitDetermination представляет собой ответ на вопрос: « Какова лучшая прибыль, которую мы можем получить от продажи вин с ценами, хранящимися в массиве p, когда текущий год - год, а интервал непроданных вин проходит через [начало , конец], включительно? Вы всегда должны пытаться создать такой вопрос для своей функции возврата, чтобы узнать, правильно ли вы это поняли и точно понимаете, что он делает.

Определение состояния:
Состояние - это количество параметров, используемых в решении DP. На этом этапе нам нужно подумать о том, какие из аргументов, которые вы передаете функции, являются избыточными, т. Е. Мы можем построить их из других аргументов или вообще не нуждаемся в них. Если есть такие аргументы, нам не нужно передавать их функции, мы будем вычислять их внутри функции.

В примере функции profitDetermination показано выше, аргумент year является излишним. Это эквивалентно количеству вин, которые мы уже продали, плюс один. Его можно определить, используя общее количество вин с начала минус количество вин, которые мы не продали, плюс один. Если мы храним общее количество вин n в качестве глобальной переменной, мы можем переписать эту функцию как:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

Нам также необходимо подумать о том, какой диапазон возможных значений параметров может получить от действительного ввода. В нашем примере каждый из параметров begin и end может содержать значения от 0 до n-1 . В действительном вводе мы также ожидаем begin <= end + 1 . Могут быть O(n²) разные аргументы, с которыми можно вызвать нашу функцию.

запоминание:
Сейчас мы почти закончили. Чтобы преобразовать решение backtrack с временной сложностью в меморандум с временной сложностью , мы будем использовать небольшой трюк, который не требует больших усилий.

Как отмечалось выше, существуют только различные параметры, с которыми можно вызвать нашу функцию. Другими словами, есть только разные вещи, которые мы можем реально вычислить. Так где же сложность времени возникает и что она вычисляет!

Ответ таков: экспоненциальная временная сложность возникает из повторной рекурсии, и из-за этого она вычисляет одни и те же значения снова и снова. Если вы запустили упомянутый выше код для произвольного массива из n = 20 вин и вычислили, сколько раз была функция, вызываемая для аргументов begin = 10 и end = 10 , вы получите номер 92378 . Это огромная трата времени, чтобы вычислить тот же ответ, который много раз. Что мы можем сделать, чтобы улучшить это, так это сохранить значения, как только мы их вычислили, и каждый раз, когда функция запрашивает уже рассчитанное значение, нам не нужно снова запускать всю рекурсию. У нас будет массив dp [N] [N] , инициализируйте его с помощью -1 (или любого значения, которое не будет получено в нашем вычислении), где -1 означает, что значение еще не было рассчитано. Размер массива определяется максимально возможным значением начала и конца, так как мы будем хранить соответствующие значения определенных начальных и конечных значений в нашем массиве. Наша процедура будет выглядеть так:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

Это наше требуемое решение DP. С помощью нашего простого трюка решение выполняется времени, потому что есть различные параметры, с которыми наша функция может быть вызвана с и для каждого из них, функция запускается только один раз с сложность.

Summery:
Если вы можете определить проблему, которая может быть решена с помощью DP, выполните следующие шаги для создания решения DP:

• Создайте функцию backtrack, чтобы обеспечить правильный ответ.
• Удалите лишние аргументы.
• Оценить и минимизировать максимальный диапазон возможных значений параметров функции.
• Попытайтесь оптимизировать временную сложность одного вызова функции.
• Сохраните значения, чтобы вам не приходилось его вычислять дважды.

Сложность решения DP: диапазон возможных значений, которые функция может вызывать с * временной сложностью каждого вызова .