Обзор
Одной из основных целей при решении проблемы является минимизация объема вычислений, чтобы мы могли быстрее найти решение. Это идея динамического программирования.
Давайте разберемся в этом на простом примере. Возможно, вы знакомы с хорошо известным рядом — рядом Фибоначчи.
Ряд Фибоначчи выглядит следующим образом:
0, 1, 1, 2, 3, 5, 8, 13…
Ряд начинается с 0, за которым следует 1, а затем вычисляется следующий член путем сложения двух последних членов ряда.
Пусть T(i) — i-й член ряда.
T(1)= 0
T(2)=1
T(3)= T(2)+T(1) = 1+0=1
T(4)=T(3)+T(2)= 1+1=2
И так далее.
Как видите, мы можем представить ряд следующим рекуррентным соотношением:
T(n)=T(n-1)+T(n-2) , n>2
Т(1)=0 и Т(2)=1
Теперь предположим, что мы хотим вычислить шестое число Фибоначчи. Схематичное представление расчета будет выглядеть так:
Как видно из диаграммы, мы вычисляем одни и те же числа несколько раз. Или мы можем сказать, что вычисление n-го числа Фибоначчи имеет перекрывающиеся подзадачи. Это явно неэффективно, и если мы это запрограммируем, оно будет использовать дополнительное пространство памяти, а также дополнительное время для вычислений.
Примечание. Мы используем подход «сверху вниз», т. е. начинаем с T(n) и двигаемся к T(n-1), T(n-2)… и так далее.
Эту проблему легко решить с помощью динамического программирования. Идея состоит в том, чтобы сохранить значение подзадачи по мере ее вычисления, а затем повторно использовать ее позже вместо повторного вычисления. Это называется запоминание. Используя этот и восходящий подход, мы теперь можем эффективно вычислить n-е число Фибоначчи.
Теперь мы начинаем с n=1 и продолжаем вычислять T(n), увеличивая n и сохраняя его. В любой момент для вычисления срока мы просто используем сохраненные значения двух последних чисел и добавляем их. Таким образом, избегая пересчета подзадач.
Это очень простой случай, когда для эффективного поиска решения используется динамическое программирование. Однако эту методологию можно использовать для решения другой категории проблем, называемых проблемами оптимизации.
Давайте посмотрим на пример.
Самая длинная общая подпоследовательность
(ЛКС)
Постановка задачи:
Даны две строки, найти самую длинную общую подпоследовательность. Символы в подпоследовательности не обязательно должны быть последовательными, но должны быть в том же порядке, что и в строке.
Например,
Строка 1: AXBXC
Строка 2: азбука
ЛКС: азбука
Подход:
Обозначим длину ЛВП через
ЛСК(AXBXC,ABC)
Задачу вычисления длины можно разделить на подзадачи, как показано ниже:
Начнем со сравнения последних символов обеих строк.
Дело 1:
Последний символ строки 1 (C) и символ строки 2 (C) совпадают, поэтому он должен присутствовать в LCS.
МНК(AXBXC,ABC) = 1+ НСК(AXBX,AB)
Случай 2:
Последний символ «AXBX» и «AB» отличаются.
НСК(AXBX,AB) = макс( НСК(AXB,AB) , НСК(AXBX,A))
Следуя той же процедуре,
МНК(AXB,AB) = 1 + НСК(AX,A)
LCS(AXBX,A) = max( LCS(AXB,A) , LCS(AXBX, null)) = LCS(AXB,A)
Примечание: LCS(строка1, строка2) = 0, если любая из строк пуста.
НСК(AX,A) = max( НСК(A,A) , НСК(AX, null)) = НСК(A,A) = 1
LCS(AXB,A) = max( LCS(AX,A) , LCS(AXB, null)) = LCS(AX,A) =1
Примечание. LCS(AX,A) — это перекрывающаяся подзадача.
Подставляя значения,
НСК(AXBXC,ABC) = 1+ макс(1+1,1) = 3
Как вы могли заметить, эту задачу оптимизации можно разделить на оптимальную подструктуру. Затем решение можно найти, используя значение подструктуры.
Рекуррентное соотношение можно сформулировать следующим образом:
НСК(i, j)
= LCS(i-1, j-1) + 1, если a[i] == b[j]
= max(LCS(i, j-1),LCS(i-1, j)) если a[i] != b[j]
= 0 if i = 0 or j = 0
( a[i] обозначает i-й символ в строке a )
Теперь для вычисления LCS(m, n) можно использовать восходящий подход ( m — длина строки a, а n — длина строки b).
Псевдокод:
Итак, это было упрощенное объяснение динамического программирования. Для тех, кому интересно, вы можете прочитать о том, как динамическое программирование применяется к таким задачам, как Cutting Rod, 0–1 Knapsack, Matrix Multiplication и т. д.
