Динамическое программирование
Динамическое программирование — это методика компьютерного программирования, которая помогает эффективно решать класс задач, имеющих перекрывающиеся подзадачи и оптимальные свойства подструктуры. Такие проблемы включают в себя многократное вычисление значения одних и тех же подзадач для нахождения оптимального решения.
Пример динамического программирования
Возьмем случай генерации последовательности Фибоначчи . Если последовательность F (1) F (2) F (3) . F (50), то следует правило F (n) = F (n-1) + F (n-2)
F(50) = F(49) + F(48)
F(49) = F(48) + F(47)
F(48) = F(47) + F(46)
. Обратите внимание, что здесь существуют перекрывающиеся подзадачи, потому как нам нужно вычислить F (48), чтобы вычислить, как F (50), так и F (49). Это именно тот алгоритм, где хорошо виден пример динамического программирования.
Как работает Динамическое программирование
Динамическое программирование работает путем сохранения результатов подзадач, чтобы, когда требуются их решения, они были под рукой, и нам не нужно было их пересчитывать. Эта техника хранения значения подзадач называется мемоизацией (запоминанием) . Сохраняя значения в массиве, мы экономим время для вычислений подзадач, с которыми мы уже сталкивались.
var m = map(0 → 0, 1 → 1) function fib(n) if key n is not in map m m[n] = fib(n − 1) + fib(n − 2) return m[n]Динамическое программирование путем мемоизации - это нисходящий подход к динамическому программированию. Изменив направление, в котором работает алгоритм, то есть начав с базового случая и работая над решением, мы можем также использовать Динамическое программирование «снизу вверх» .
function fib(n) if n = 0 return 0 else var prevFib = 0, currFib = 1 repeat n − 1 times var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFibРекурсия vs Динамического программирования
Динамическое программирование в основном применяется к рекурсивным алгоритмам. Это не совпадение, большинство задач оптимизации требуют рекурсии, а для оптимизации используется динамическое программирование. Но не все задачи, использующие рекурсию, могут использовать Динамическое программирование. Если нет перекрывающихся подзадач, как в случае последовательности Фибоначчи, рекурсия может достичь решения только с использованием подхода «разделяй и властвуй» . По этой причине рекурсивный алгоритм, такой как «Сортировка слиянием» , не может использовать динамическое программирование, поскольку подзадачи никоим образом не перекрываются.
Жадные алгоритмы vs Динамического программирования
Жадные алгоритмы похожи на динамическое программирование в том смысле, что они оба являются инструментами для оптимизации. Однако жадный алгоритм ищет локально оптимальное решение или, другими словами, «жадный» выбор в надежде найти глобальный оптимум. Следовательно, жадные алгоритмы могут сделать предположение, которое выглядит оптимально, но в то же время становится дорогостоящим и не гарантирует нахождение глобального оптимума. Динамическое программирование, с другой стороны, находит оптимальное решение для подзадач, а затем делает осознанный выбор, комбинируя результаты этих подзадач, чтобы найти наиболее оптимальное решение.
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
По статье задано0 вопрос(ов)
5.8 Жадные алгоритмы и динамическое программирование
Итак, что же представляют собой жадные алгоритмы? Перед тем, как ответить на этот вопрос, отве- тим на другой: а что же есть алго- ритм? Кажется, интуитивно мы это понимаем, однако интуиция имеет свойство подводить в самый не- подходящий момент, причем очень незаметно.
Просто алгоритмом будем назы- вать механизм, который должен га- рантировать не только то, что ре- шение будет найдено, но и то, что будет найдено именно оптималь- ное решение. Кроме того, алго- ритм должен обладать следующи- ми качествами:
- Ограниченность по времени (работа алгоритма должна прекратиться за разумное время);
- Правильность (алгоритм должен находить правильное решение);
- Детерминистичность (сколько бы раз не исполнялся алгоритм с одинаковыми входными дан- ными, результат должен быть один и тот же);
- Конечность (описание работы алгоритма должно содержать конечное число шагов);
- Однозначность (каждый шаг алгоритма должен интерпретироваться однозначно).
5.8.1 Задача о выборе заявок
Пусть подано N заявок на прове- дение занятий в одной и той же ау- дитории. Для каждого занятия из- вестно время его проведения [bi,ei], где bi – время начала заня- тия, еi – время окончания. Два раз- ных занятия не могут перекры- ваться по времени, но условимся, что начало одного может совпа- дать с окончанием другого. Зада- ча состоит в том, чтобы выбрать максимальное число совместимых по времени занятий. Жадный алгоритм поступает так: упорядочим заявки в порядке воз- растания времени окончания: .На сортировку понадобится време- ни O(N log(N)) в худшем случае. Так как в этой статье проблема сортировки не рассматривается, положим, что массив уже отсорти- рован по возрастанию. Далее все предельно просто: var b,е: array[1..100] of integer; А: set of byte; i,j,n: integer; begin read(n); for i:=1 to n do read(b[i],e[i]); А := [1]; j := 1; for i:=2 to n do if b[i]>=е[j] then begin (если i-й отрезок лежит npaвee j-го) А:=А+[i]; (то включаем j-й ) j := i; (и запоминаем его как самый правый в множестве А) end; for i:=1 to n do (выводим результат) if (i in А) then writeln(i); end. Листинг 5.21 – Задача о выборе заявок, рещаемая «жадным» алгоритмом Вначале А содержит заяв- ку j=1. Далее в цикле по i ищется заявка, начинающаяся не рань- ше, чем оканчивается заявка j. Если таковая найдена, она вклю- чается в множество А, и перемен- ной j присваивается ее номер. Ал- горитм требует всего лишь O(n) шагов (без учета предваритель- ной сортировки). Жадность этого алгоритма состоит в том, что на каждом шаге он делает выбор так, чтобы остающееся свобод- ным время было максимальным (это и есть локально-оптималь- ный выбор). Теперь докажем, что этот алго- ритм дает оптимальное решение. Прежде всего, докажем, что суще- ствует оптимальное решение за- дачи о выборке заявок, содержа- щее заявку 1 (с самым ранним временем окончания). В самом деле, если в каком-то оптималь- ном множестве заявок заявка 1 не содержится, то можно заменить в нем заявку с самым ранним вре- менем окончания на заявку 1, что не повредит совместности заявок, (ибо заявка 1 кончается еще раньше, чем прежняя, и ни с чем пере- сечься не может) и не изменит их общего количества. Стало быть, можно искать оптимальное мно- жество заявок А среди содержащих заявку 1. После того, как мы договорились рассматривать только наборы, содержащие заяв- ку 1, все несовместные с ней за- явки можно выкинуть, и задача сводится к выбору оптимального набора заявок из множества ос- тавшихся заявок (совместных с заявкой 1). Другими словами, мы свели задачу к аналогичной зада- че с меньшим числом заявок. Pac суждая по индукции, получаем, что, делая на каждом шаге жад- ный выбор, мы придем к опти- мальному решению. Вспомним динамическое про- граммирование и попробуем ре- шить ту же задачу с помощью не- го. Заведем динамическую табли- цу m[1..n], где m[i] означает мак- симальное число совместных за- явок среди набора с номерами 1..i. Допустим, что подзадачи m[1], m[2]. m[k1] уже реше- ны. Установим рекуррентную за- висимость для решения задачи m[k]: k-й отрезок можно брать, а можно и не брать в искомое мно- жество. Если мы его не берем, то m[k] = m[k1], а если мы его бе- рем, то m[k] = 1 + m[ max( i такое, что e[i] ≤ s[k]) ] Последнее выражение означает, что мы отбросили все заявки, не- совместные с k‑й (левее нее), взя- ли оптимум для оставшегося мно- жества из динамической таблицы плюс заявку k. Таким образом, рекуррентная зависимость такова m[k] = max< m[k1], 1 + m[max(i та- кое, что e[i] ≤ b[k]) ]) Для того, чтобы найти оптимальное множество (а не только количество m[n] элементов в нем), надо завес- ти дополнительный массив рrеv[1..n], где prev[k] будет озна- чать предыдущий элемент, (если мы k-й брали), или 1 (если не бра- ли k-й). Покажем, как выглядит ре- ализация ДП-алгоритма, а потом сделаем его оценку. var b,е,m,prev: array[0..100] of integer; i,j,k,n: integer; b egin read(n); for i:=1 to n do read(b[i],e[i]); fillchar(prev, sizeof(prev), $FF);(заполняем -1) m [0] := 0; for k:=2 to n do begin i:= k-1; (ищем i такое, что e[i]=b[k]) while (i>0) and (е[i] >b[k] ) do dec(i); if m[k-1] >= 1 + m[i] then (если элемент лучше не брать) m[k] := m[k-1] (то не берем его) else begin m[k]:= 1 + m[i]; (иначе берем и) prev[k] := i; (запоминаем, что перед ним идет элемент i) end; end; i:=n; (пробежимся с конца до начала и выведем все элементы) repeat if рrеv[i] =-1 then dec(i) (если i-Й не брали, движемся дальше) еlsе begin (в противном случае) writeln(i); (выводим этот и) i:= prev[i); (перепрыгиваем через несовместимые слева от него) end; until i=0; end. Листинг 5.22 – Задача о выборе заявок, рещаемая ДП-алгоритмом Даже не делая оценок сложности, легко видеть, что ДП-алгоритм сложнее жадного. Ну, а если быть более точным, то его сложность равняется O(n 2 ), так как существу- ет два вложенных цикла (for по k и внутренний while, который делает в с реднем порядка O(n) сравнений и уменьшений i). К тому же он требу- ется порядка O(n) дополнительной памяти. Таким образом, в этом слу- чае жадный алгоритм намного эф- фективнее динамического прог- раммирования.