Интуитивно понятное руководство по популярной технике оптимизации.

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

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

Оглавление

When is DP used?
  - Overlapping Sub-problems
  - Optimal Substructure
The Two kinds of DP
  - The top-down approach
  - The bottom-up approach
An example
  - The Problem
  - The analysis
  - A recursive Solution
  - The base case
  - A dynamic programming approach
  - Improving the Algorithm

Когда используется DP?

Задача должна удовлетворять двум необходимым условиям для работы DP.

  • Перекрывающиеся подзадачи
  • Оптимальная подконструкция

Давайте рассмотрим их более подробно.

Перекрывающиеся подзадачи

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

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

Если вы ищете конкретную страницу в книге, что бы вы сделали? Вы открываете книгу на определенной странице и сравниваете номер страницы, на которой находитесь, с номером страницы, которую ищете.

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

Вы будете продолжать, пока не найдете страницу.

Если бы вам пришлось смоделировать это как рекурсивную функцию, как бы это выглядело? Может что-то вроде этого.

Примечание. Следующие ниже фрагменты были написаны в форме псевдокода для повышения удобочитаемости

Довольно просто. Существует функция getpage, которая возвращает страницу (target_page, здесь), которую мы ищем. Функция просматривает среднюю страницу между from_page и to_page и проверяет, есть ли совпадения.

Если нет, функция смотрит либо на левую, либо на правую половину рассматриваемого раздела.

Но что представляют собой эти два рекурсивных вызова getpage? Вы заметите, что при каждом рекурсивном вызове мы сокращаем пространство поиска вдвое. Мы решаем ту же проблему, то есть ищем конкретную страницу в меньшем пространстве. Решаем подзадачи.

Алгоритмы Разделяй и властвуй или DAC работают по принципу подзадач. Часть «разделить» относится к разделению проблемы на подзадачи. Алгоритмы сортировки, такие как сортировка слиянием и быстрая сортировка, являются отличными примерами. Обратите внимание, что бинарный поиск - это не совсем алгоритм DAC по той простой причине, что в нем нет шага «комбинирования», в то время как реальный алгоритм «разделяй и властвуй» будет комбинировать результаты своих подзадач, чтобы получить окончательное решение.

Теперь, когда мы ответили на вопрос, что такое подзадача, мы переходим к другому слову: «перекрытие».

Когда эти подзадачи необходимо решать более одного раза, говорят, что они перекрывают друг друга. Посмотрите на график вызовов для вычисления значения n-го члена Фибоначчи.

Рекуррентное отношение:

the relation
f(n) = f(n - 1) + f(n-2)
the base case
f(0) = 0
f(1) = 1

Вызовы затенены, чтобы обозначить перекрывающиеся подзадачи. Сравните это с чем-то вроде бинарного поиска, где подзадачи не пересекаются.

Оптимальное свойство каркаса

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

Быстрый пример? Допустим, вы хотите найти кратчайший путь от A до B. Пусть X будет промежуточной точкой между A и B с одинарным ребром, соединяющим его с A.

Чтобы решить эту проблему, мы можем найти кратчайший путь от всех промежуточных узлов (X) до B, а затем найти путь от A до X плюс кратчайший путь от X до B, самый короткий для всех X.

shortest(A, B) = min(AX + shortest(X, B)) for all intermediate nodes X.

Здесь мы используем оптимальное промежуточное решение (кратчайшее (X, B)) и используем его (в отличие от рассмотрения каждого решения для подзадачи). чтобы найти окончательный оптимальный ответ.

Два вида DP

Подход сверху вниз (мемоизация)

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

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

Подход снизу вверх (табулирование)

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

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

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

Для сравнения, давайте посмотрим на возможную нисходящую и восходящую функцию, которая возвращает n-й член Фибоначчи.

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

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

Пример

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

Эта проблема

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

example 1:
[1, 2, 3]    => 1 + 3 = 4
example 2:
[1, 1, 1, 1] => 1 + 1 = 2
example 3:
[2, 5, 2]    => 5 = 5

Анализ

Сначала попробуем жадный подход.

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

Этот подход может работать в определенных случаях.

[1, 5, 1, 10, 1, 5, 1]

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

Затем мы выбираем обе пятерки, поскольку они являются следующими по величине элементами, и игнорируем их соседей. На этом наш алгоритм заканчивается, так как не осталось никаких элементов. Полученный результат - 10 + 5 + 5 - и есть правильный ответ.

Но это не всегда срабатывает. Возьмем следующий пример:

[1, 1, 9, 10, 9, 1, 1]

На каждом шаге, если вы выбираете максимальный элемент, игнорируете его соседей и продолжаете таким образом, вы в конечном итоге выбираете 10, затем 1, а затем снова 1 после игнорирования обеих 9, что в сумме дает 12, но правильный ответ будет 1 + 9 + 9 + 1, что равно 20.

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

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

Рекурсивное решение

Поразмыслив немного, вы, вероятно, увидите, что у нас есть одно условие, о котором следует помнить: никаких смежных элементов. Вы, наверное, догадались, что:

  • мы можем выбрать либо рассматривать элемент в нашей сумме, либо игнорировать его
  • если мы его рассмотрим, нам придется игнорировать соседний с ним элемент

Для краткости пусть f (a..b) представляет вызов f нашего массива из index a для индексации b (оба включительно). Эта функция f будет представлять нашу рекурсивную функцию, которая решит проблему.

Итак, f (0..4) будет означать запуск функции от индекса 0 до индекса 4.

Две стрелки, указывающие из ячейки, представляют наш выбор последующих вызовов функций. Поскольку это задача максимизации, нам придется выбрать максимум из этих вариантов.

Вернемся к нашему массиву.

[5, 10, 100, 10, 5]

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

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

f(0..4)

Для элемента с индексом 0 (который здесь равен 5) мы можем выбрать одно из следующих действий:

  • включите его в нашу сумму: наша текущая сумма будет тогда 5 + максимальная сумма остальной части массива, но без учета следующего элемента (индекс 1). Таким образом, наша сумма становится 5 + f (2..4). Или, чтобы обобщить это, arr [0] + f (2..4)
  • исключить его: наша текущая сумма будет тогда просто равна максимальной сумме оставшегося массива. Это можно записать как: 0 + f (1..4). Обратите внимание, что наш следующий вызов исходит из индекса 1, а не из 2, как в предыдущем случае. Поскольку мы не рассматриваем элемент с индексом 0, мы можем рассматривать элемент с индексом 1 - нас не заставляют игнорировать его.

График здесь наглядно объясняет это. Как упоминалось ранее, все стрелки на данном уровне представляют наш выбор, из которого мы выбираем самый лучший.

Итак, наш окончательный ответ:

f(0..4) = max(arr[0] + f(2..4), f(1..4))

Давайте расширим это для следующей итерации.

Сначала мы сделаем это для левого дерева, которым является f (2..4). Это похоже на то, что мы сделали при первом вызове f. Помните, что часть arr [0] + все еще там. Он будет добавлен к значению f (2..4) на нашем пути вверх по дереву вызовов.

Наш выбор:

  • рассмотрим arr [2] в нашей сумме: наша сумма на этом этапе становится arr [2] + f (4..4) . Помните, что, поскольку мы рассматриваем элемент с индексом 2, нам придется игнорировать следующий элемент - индекс 3.
  • ignore arr [2]: наша сумма равна максимальному результату оставшегося массива без необходимости игнорировать соседний элемент. Итак, это f (3..4).

Как и раньше, значение f (2..4) будет максимальным из двух возможных вариантов.

f(2..4) = max(arr[2] + f(4..4), f(3..4))

Базовый вариант

Как вы думаете, что оценивает f (4..4)? Следуя нашим обозначениям, это результат вызова нашей функции для массива от индекса 4 до… ну, индекса 4. Это означает, что мы вызываем функцию для одного элемента. Максимальная сумма одного элемента - это он сам.

Еще одна вещь, о которой следует помнить: в f (a..b) значение a никогда не должно быть больше b. Поскольку этот вызов представляет начало с индекса a и переход к индексу b, нам нужно будет вернуть 0, если a когда-либо станет больше, чем b . Если нет элементов, максимальной суммы не существует.

У нас есть базовый вариант. Наша функция f, когда вызывается для одного элемента, вернет этот элемент напрямую и вернет 0, если мы находимся за пределами допустимого диапазона. Дальнейших рекурсивных вызовов нет. Вот почему это называется базовым случаем.

В нашем случае наш вызов f (3..4) приводит к недопустимому вызову f (5..4) , который мы обрабатываем, возвращая 0. Мы обобщим это позже.

f(4..4) = arr[4]
f(5..4) = 0

Отношение повторения

Давайте еще раз посмотрим на наши результаты.

first call:
f(0..4) = max(arr[0] + f(2..4), f(1..4))
second call:
f(2..4) = max(arr[2] + f(4..4), f(3..4))
the base case:
f(4..4) = arr[4]
f(5..4) = 0

Заметили закономерность в первых двух результатах? Если мы их обобщим, то получим:

f(a..b) = max(arr[a] + f(a+2 .. b), f(a+1, b))

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

Они не меняются. Нет никаких b + 1 или b + 2. Это всегда b. И каково значение b при первом звонке? Последний индекс. Поскольку b является постоянным во всем алгоритме, мы можем удалить его.

Наше рекуррентное отношение становится:

f(a) = max(arr[a] + f(a+2), f(a+1))

где f (a) - это вызов массива, начиная с индекса a и далее.

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

Обобщенная версия нашего базового случая:

f(n-1) = arr[n-1] where n is the size of the array
f(a) = 0 if a >= n where n is the size of the array

Таким образом, мы имеем отношение:

f(a) = max(arr[a] + f(a+2), f(a+1))
f(n-1) = arr[n-1] where n is the size of the array
f(a) = 0 if a >= n where n is the size of the array

Давайте реализуем рекурсивный подход, основанный на этом соотношении.

Эта функция будет называться так:

array := [1, 5, 2, 4, ...]
return f(array, 0)

В чем будет сложность этого?

Если бы мы приблизительно оценили сложность на основе размера массива (n), с которым мы работаем, мы получили бы что-то вроде этого:

T(n) = T(n-2) + T(n-1) + O(1)
T(0) = O(1)

Интуитивно понятно, что каждый вызов f для массива размера n - представленного как T (n) - приводит к двум вызовам f для массивов размера n-2 и n-1. То есть на каждом этапе мы удваиваем количество вызовов f.

Асимптотическая временная сложность экспоненциальна. Исходя из приведенных выше рассуждений, мы получаем O (2 ^ n).

Это приблизительная оценка верхней границы, поскольку дерево n-2 должно заканчиваться до n-1 tree, поэтому мы делаем несколько меньше, чем удвоение вызовов. Фактическая сложность: O (phi ^ n) - phi - золотое сечение - или O (1,618 ^ n), , что немного меньше нашей первоначальной оценки, но давайте придерживаться O (2 ^ n).

Еще одна вещь, на которую следует обратить внимание, это то, что приведенное выше отношение рекуррентности похоже на отношение n-го члена Фибоначчи, что, следовательно, дает аналогичную сложность.

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

Вот где на сцену выходит динамическое программирование.

Если вы присмотритесь, вы увидите частично совпадающие подзадачи, о которых мы говорили ранее.

Теперь наступает важная часть - преобразование этой рекурсивной реализации в подход динамического программирования. Что, если бы мы сохранили значения повторяющихся вызовов функций?

Давайте сохраним массив, где i-й элемент - это значение f (i), которое, в свою очередь, является максимальной суммой массива из индекса i до конца.

dp[i] = f(i..n) = f(i)

И поскольку у нас уже есть результат для f (i),

dp[i] = max(arr[i] + f(i + 2), f(i + 1))

Теперь, когда у нас есть это отношение, мы можем пойти двумя разными путями. Либо мы идем по нисходящему маршруту, где наша функция все еще рекурсивна, как наш результат выше, либо мы удаляем все рекурсивные вызовы и идем по восходящему маршруту.

Мы сосредоточимся на восходящем маршруте, но давайте обсудим нисходящий подход.

- Подход сверху вниз

Посмотрите на наш предыдущий результат.

dp[i] = max(arr[i] + f(i + 2), f(i + 1))

Это все, что нам нужно для реализации подхода сверху вниз. Для любого вызова f мы сначала проверяем в нашем массиве dp, если мы уже сделали этот вызов ранее, и если у нас есть, мы напрямую используем предварительно рассчитанное значение.

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

Дерево вызовов должно выглядеть примерно так:

Давайте реализуем этот алгоритм.

Дополнительное пространство, необходимое для хранения результатов наших подзадач, линейно растет с размером входного массива. Следовательно, помимо пространства O (n), необходимого из-за рекурсивного стека, у нас есть O (n) пространство для массива dp, где n - размер входного массива.

Временная сложность, хотя ее труднее вычислить, линейна по отношению к размеру входных данных. Это потому, что мы храним ответы на подзадачи, которые мы уже решили, и поэтому у нас есть O (n) уникальных подзадач, которые мы должны решить. . Этот результат также можно проверить с учетом сложности, которую мы получаем при использовании восходящего подхода.

- Подход снизу вверх

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

Давайте заменим другие вызовы f элементами доступа dp.

dp[i] = max(arr[i] + dp[i + 2], dp[i + 1])

Как насчет базового случая f (n-1) = arr [n-1]? Это будет последний элемент массива dp.

dp[n-1] = arr[n-1]

И вот так у нас есть решение для восходящего dp подхода!

Давайте реализуем это так же, как мы это сделали для рекурсивного подхода.

Эта функция будет называться так:

array := [1, 5, 2, 4, ...]
output(f(array))

Сложность здесь будет линейной как в пространстве, так и во времени.

Почему?

Мы запускаем один цикл for n-1 раз, и на каждой итерации мы выполняем операции с постоянным временем - линейная временная сложность.

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

Улучшение алгоритма

Но можем ли мы сделать лучше? Давайте посмотрим.

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

Но как насчет космической сложности? Нужно ли нам поддерживать массив размером n для решения проблемы?

Посмотрите внимательно на строку внутри цикла for:

dp[i] = max(arr[i] + dp[i + 2], dp[i + 1])

В любой момент все, что нам нужно для заполнения dp [i], - это следующие два элемента в dp - по индексам i +1 и i + 2. Нет причин сохранять все наши результаты. Нам просто нужно отслеживать последние две итерации.

Давайте использовать здесь три переменные. Назовем их i_0, i_1 и i_2. чтобы облегчить отношения между ними.

dp[i]   --> i_0
dp[i+1] --> i_1
dp[i+2] --> i_2

Обратите внимание, что на следующей итерации нашего цикла наш счетчик цикла i , становится i + 1, поскольку мы уменьшаем i на каждой итерации. dp [i +1] будет следующим dp [i +2], dp [i] будет следующим dp [i +1] и dp [i + 2] - который нам не понадобится, поскольку dp [i +3] не требуется - можно повторно использовать в качестве следующего dp [i].

Заменив это нашими тремя новыми переменными, код внутри нашего цикла станет:

i_0 := max(arr[i] + i_2, i_1)
i_2 := i_1
i_1 := i_0

Мы инициализируем эти переменные так же, как нашу реализацию массива.

dp[n-1] = arr[n-1] --> i_1 = arr[n-1]
dp[n] = 2          --> i_2 = 0

И последнее, о чем следует помнить: что, если входной массив содержит только один элемент? Наш цикл, который выполняется от n-2 до 0, не будет выполнен ни разу.

Следовательно, мы инициализируем i_0 значением i_1. Поэтому, если цикл никогда не запускается - входной массив имеет только один элемент - возвращение i_0 вернет значение i_1 , который является единственным элементом массива.

Наконец, мы возвращаем i_0 вместо dp [0].

return dp[0] --> return i_0

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

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

array := [1, 5, 2, 4, ...]
return f(array)

Для массива любой длины все, что нам нужно, - это три переменные. Таким образом, пространственная сложность нашего алгоритма теперь O (1) - постоянная.

Подводя итоги,

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

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

Лучшим случаем является восходящий подход, требующий O (1) пробела - это означает, что пространство, используемое нашим алгоритмом dp, не изменяется с размером ввода n.

Код

Давайте реализуем наш окончательный алгоритм восходящего динамического программирования с постоянным пространством на C ++. Имена переменных и функций такие же, как и раньше.

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

Заключение

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