Вступление
Динамическое программирование обычно используется для оптимизации рекурсивных алгоритмов, поскольку они имеют тенденцию экспоненциально масштабироваться. Основная идея состоит в том, чтобы разбить сложные проблемы (с множеством рекурсивных вызовов) на более мелкие подзадачи, а затем сохранить их в памяти, чтобы нам не приходилось пересчитывать их каждый раз, когда мы их используем.
Чтобы понять концепции динамического программирования, нам нужно познакомиться с несколькими предметами:
- Что такое динамическое программирование?
- Алгоритм резки штанги
- Упрощенная задача о рюкзаке
- Традиционная задача о рюкзаке
- Левенштейн Расстояние
- LCS - самая длинная общая подпоследовательность
- Другие проблемы, связанные с динамическим программированием
- Заключение
Что такое динамическое программирование?
Динамическое программирование - это принцип программирования, при котором очень сложная проблема может быть решена путем разделения ее на более мелкие подзадачи. Этот принцип очень похож на рекурсию, но с одним ключевым отличием каждая отдельная подзадача должна быть решена только один раз .
Чтобы понять, что это означает, мы сначала должны понять проблему решения рекуррентных отношений. Каждую сложную проблему можно разделить на очень похожие подзадачи, это означает, что мы можем построить рекуррентное отношение между ними.
Давайте посмотрим на пример, с которым все мы знакомы, последовательность Фибоначчи ! Последовательность Фибоначчи определяется следующим рекуррентным соотношением :
$$
фибоначчи (n) = фибоначчи (n-1) + фибоначчи (n-2)
$
Примечание: рекуррентное отношение - это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов. Последовательность Фибоначчи - отличный тому пример.
Итак, если мы хотим найти n-th число в последовательности Фибоначчи,
мы должны знать два числа, предшествующих n-th в последовательности.
Однако каждый раз, когда мы хотим вычислить другой элемент последовательности Фибоначчи, у нас есть определенные повторяющиеся вызовы в наших рекурсивных вызовах, как видно на следующем изображении, где мы вычисляем Фибоначчи (5) :
{.ezlazyload}
Например, если мы хотим вычислить F (5), нам, очевидно, необходимо вычислить F (4) и F (3) в качестве предварительного условия. Однако для вычисления F (4) нам необходимо вычислить F (3) и F (2), что, в свою очередь, требует от нас вычисления F (2) и F (1), чтобы получить F (3) - и так далее.
Это приводит к множеству повторяющихся вычислений, которые, по сути, являются избыточными и значительно замедляют алгоритм. Чтобы решить эту проблему, мы знакомимся с динамическим программированием .
В этом подходе мы моделируем решение так, как если бы мы решали его рекурсивно, но мы решаем его с нуля, запоминая решения подзадач (шаги), которые мы предпринимаем для достижения вершины.
Следовательно, для последовательности Фибоначчи мы сначала решаем и запоминаем F (1) и F (2), затем вычисляем F (3), используя два мемоизированных шага, и так далее. Это означает, что вычисление каждого отдельного элемента последовательности составляет O (1) , потому что мы уже знаем первые два.
При решении задачи с помощью динамического программирования мы должны выполнить три шага:
- Определите рекуррентное отношение, применимое к указанной проблеме.
- Инициализировать начальные значения памяти / массива / матрицы
- Убедитесь, что когда мы делаем «рекурсивный вызов» (получаем доступ к запомненному решению подзадачи), он всегда решается заранее.
Следуя этим правилам, давайте рассмотрим несколько примеров алгоритмов, использующих динамическое программирование.
Алгоритм резки штанги
Начнем с простого:
Дан стержень длины
nи массив, содержащий цены на все части размером меньшеn. Определите максимальную ценность, которую можно получить, разрезая стержень и продавая его по частям.
Наивное решение
Эта проблема практически адаптирована для динамического программирования, но поскольку это наш первый реальный пример, давайте посмотрим, сколько огней мы можем запустить, запустив этот код:
public class naiveSolution {
static int getValue(int[] values, int length) {
if (length <= 0)
return 0;
int tmpMax = -1;
for (int i = 0; i < length; i++) {
tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1));
}
return tmpMax;
}
public static void main(String[] args) {
int[] values = new int[]{3, 7, 1, 3, 9};
int rodLength = values.length;
System.out.println("Max rod value: " + getValue(values, rodLength));
}
}
Выход:
Max rod value: 17
Это решение, хотя и правильное, очень неэффективно . Рекурсивные вызовы не запоминаются, поэтому плохой код должен решать одну и ту же подзадачу каждый раз, когда есть одно перекрывающееся решение.
Динамический подход
Используя тот же базовый принцип, что и выше, но добавляя мемоизацию и исключая рекурсивные вызовы, мы получаем следующую реализацию:
public class dpSolution {
static int getValue(int[] values, int rodLength) {
int[] subSolutions = new int[rodLength + 1];
for (int i = 1; i <= rodLength; i++) {
int tmpMax = -1;
for (int j = 0; j < i; j++)
tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
subSolutions[i] = tmpMax;
}
return subSolutions[rodLength];
}
public static void main(String[] args) {
int[] values = new int[]{3, 7, 1, 3, 9};
int rodLength = values.length;
System.out.println("Max rod value: " + getValue(values, rodLength));
}
}
Выход:
Max rod value: 17
Как мы видим, результирующие результаты одинаковы, только с разной временной / пространственной сложностью.
Мы устраняем необходимость в рекурсивных вызовах, решая подзадачи с нуля, используя тот факт, что все предыдущие подзадачи данной проблемы уже решены.
Повышение производительности
Чтобы понять, насколько более эффективен динамический подход, давайте попробуем запустить алгоритм с 30 значениями.
Решение Naive заняло ~ 5,2 секунды, тогда как решение Dynamic заняло ~ 0,000095 секунды .
Упрощенная задача о рюкзаке
Проблема упрощенного рюкзака - это проблема оптимизации, для которой нет единого решения. Вопрос для этой проблемы будет - «Есть ли решение вообще?»:
По заданному набору предметов, каждый с весом
w1,w2... определите количество каждого предмета, которое нужно положить в рюкзак, чтобы общий вес был меньше или равнялся заданному пределуK
Итак, давайте сделаем шаг назад и разберемся, как мы будем представлять
решения этой проблемы. Во-первых, давайте сохраним веса всех элементов в
массиве W
Далее, предположим, что имеется n элементов, и мы пронумеруем их
числами от 1 to n , так что вес i-th элемента равен W[i] .
Мы сформируем матрицу M размеров (n+1) x (K+1) M[x][y]
соответствует решению задачи о ранце, но включает только первые x
элементов начального массива и с максимальной емкостью y .
Пример
Допустим, у нас есть 3 предмета с весом w1=2kg , w2=3kg и w3=4kg .
Используя описанный выше метод, мы можем сказать, что M[1][2] является
допустимым решением. Это означает, что мы пытаемся заполнить рюкзак
вместимостью 2 кг только первым предметом из массива веса ( w1 ).
В M[3][5] мы пытаемся заполнить рюкзак вместимостью 5 кг, используя
первые 3 элемента массива весов ( w1,w2,w3 ). Это недопустимое
решение, поскольку мы его переоснащаем.
Инициализация матрицы
При заполнении матрицы следует учитывать два момента:
Существует ли решение для данной подзадачи (M [x] [y] .exists) И включает ли данное решение последний элемент, добавленный в массив (M [x] [y] .includes).
Следовательно, инициализация матрицы довольно проста, M[0][k].exists
всегда false , если k > 0 , потому что мы не клали никаких предметов
в рюкзак вместимостью k
С другой стороны, M[0][0].exists = true , потому что рюкзак должен
быть пустым с самого начала, поскольку k = 0 , и поэтому мы не можем
ничего положить, и это правильное решение.
Кроме того, мы можем сказать, что M[k][0].exists = true но также
M[k][0].includes = false для каждого k .
Примечание. Тот факт, что решение существует для данного M[x][y]
, не обязательно означает, что эта конкретная комбинация является
решением. В случае M[10][0] решение существует - не включающее ни один
из 10 элементов. Вот почему M[10][0].exists = true но
M[10][0].includes = false .
Принцип алгоритма
Затем давайте построим рекуррентное отношение для M[i][k] с помощью
следующего псевдокода:
if (M[i-1][k].exists == True):
M[i][k].exists = True
M[i][k].includes = False
elif (kW[i]>=0):
if(M[i-1][kW[i]].exists == true):
M[i][k].exists = True
M[i][k].includes = True
else:
M[i][k].exists = False
Таким образом, суть решения состоит в разделении подзадачи на два случая:
- Когда решение существует для первых
i-1элементов, для емкостиk - Когда решение существует для первых
i-1элементов, но для мощностиkW[i]
Первый случай не требует пояснений, решение проблемы у нас уже есть.
Второй случай относится к знанию решения для первых i-1 элементов, но
емкость составляет ровно один i-th элемент, который не заполнен, что
означает, что мы можем просто добавить один i-th элемент, и у нас есть
новое решение. !
Выполнение
В этой реализации, чтобы упростить задачу, мы сделаем класс Element
для хранения элементов:
public class Element {
private boolean exists;
private boolean includes;
public Element(boolean exists, boolean includes) {
this.exists = exists;
this.includes = includes;
}
public Element(boolean exists) {
this.exists = exists;
this.includes = false;
}
public boolean isExists() {
return exists;
}
public void setExists(boolean exists) {
this.exists = exists;
}
public boolean isIncludes() {
return includes;
}
public void setIncludes(boolean includes) {
this.includes = includes;
}
}
Теперь мы можем погрузиться в основной класс:
public class Knapsack {
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
System.out.println("Insert knapsack capacity:");
int k = scanner.nextInt();
System.out.println("Insert number of items:");
int n = scanner.nextInt();
System.out.println("Insert weights: ");
int[] weights = new int[n + 1];
for (int i = 1; i <= n; i++) {
weights[i] = scanner.nextInt();
}
Element[][] elementMatrix = new Element[n + 1][k + 1];
elementMatrix[0][0] = new Element(true);
for (int i = 1; i <= k; i++) {
elementMatrix[0][i] = new Element(false);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
elementMatrix[i][j] = new Element(false);
if (elementMatrix[i - 1][j].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(false);
} else if (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
}
}
System.out.println(elementMatrix[n][k].isExists());
}
}
Единственное, что осталось, это реконструкция решения, в классе выше мы знаем, что решение СУЩЕСТВУЕТ , но не знаем, что это такое.
Для реконструкции мы используем следующий код:
List<Integer> solution = new ArrayList<>(n);
if (elementMatrix[n][k].isExists()) {
int i = n;
int j = k;
while (j > 0 && i > 0) {
if (elementMatrix[i][j].isIncludes()) {
solution.add(i);
j = j - weights[i];
}
i = i - 1;
}
}
System.out.println("The elements with the following indexes are in the solution:\n" + (solution.toString()));
Выход:
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
true
The elements with the following indexes are in the solution:
[5, 1]
Простая разновидность задачи о рюкзаке - наполнение рюкзака без оптимизации стоимости, но теперь с неограниченным количеством каждого отдельного предмета.
Этот вариант может быть решен путем простой корректировки нашего существующего кода:
// Old code for simplified knapsack problem
else if (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
// New code, note that we're searching for a solution in the same
// row (i-th row), which means we're looking for a solution that
// already has some number of i-th elements (including 0) in it's solution
else if (j >= weights[i]) {
if (elementMatrix[i][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
Традиционная задача о рюкзаке
Используя оба предыдущих варианта, давайте теперь посмотрим на традиционную задачу о рюкзаке и посмотрим, чем она отличается от упрощенного варианта:
Учитывая набор элементов, каждый с весом
w1,w2... и значениемv1,v2... определяет количество каждого элемента, который нужно включить в коллекцию, чтобы общий вес был меньше или равен заданному пределуkа общее значение должно быть как можно большим.
В упрощенной версии все решения были одинаково хороши. Однако теперь у нас есть критерии для поиска оптимального решения (или максимально возможного значения). Имейте в виду, что на этот раз у нас есть бесконечное количество каждого элемента , поэтому элементы могут встречаться в решении несколько раз.
В реализации мы будем использовать старый класс Element с добавленным
value частного поля для хранения максимально возможного значения для
данной подзадачи:
public class Element {
private boolean exists;
private boolean includes;
private int value;
// appropriate constructors, getters and setters
}
Реализация очень похожа, с той лишь разницей, что теперь нужно выбрать оптимальное решение, исходя из полученного значения:
public static void main(String[] args) {
// Same code as before with the addition of the values[] array
System.out.println("Insert values: ");
int[] values = new int[n + 1];
for (int i=1; i <= n; i++) {
values[i] = scanner.nextInt();
}
Element[][] elementMatrix = new Element[n + 1][k + 1];
// A matrix that indicates how many newest objects are used
// in the optimal solution.
// Example: contains[5][10] indicates how many objects with
// the weight of W[5] are contained in the optimal solution
// for a knapsack of capacity K=10
int[][] contains = new int[n + 1][k + 1];
elementMatrix[0][0] = new Element(0);
for (int i = 1; i <= n; i++) {
elementMatrix[i][0] = new Element(0);
contains[i][0] = 0;
}
for (int i = 1; i <= k; i++) {
elementMatrix[0][i] = new Element(0);
contains[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
elementMatrix[i][j] = new Element(elementMatrix[i - 1][j].getValue());
contains[i][j] = 0;
elementMatrix[i][j].setIncludes(false);
elementMatrix[i][j].setValue(M[i - 1][j].getValue());
if (j >= weights[i]) {
if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) {
if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) {
elementMatrix[i][j].setIncludes(true);
elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]);
contains[i][j] = contains[i][j - weights[i]] + 1;
}
}
}
System.out.print(elementMatrix[i][j].getValue() + "/" + contains[i][j] + " ");
}
System.out.println();
}
System.out.println("Value: " + elementMatrix[n][k].getValue());
}
Выход:
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
Insert values:
1 2 3 4 5
0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/0 0/0 0/0
0/0 0/0 0/0 0/0 0/0 0/0 0/0 2/1 0/0 1/0 0/0 0/0 0/0
0/0 0/0 0/0 0/0 3/1 0/0 0/0 2/0 6/2 1/0 0/0 5/1 9/3
0/0 0/0 0/0 0/0 3/0 0/0 0/0 2/0 6/0 1/0 4/1 5/0 9/0
0/0 0/0 0/0 5/1 3/0 0/0 10/2 8/1 6/0 15/3 13/2 11/1 20/4
Value: 20
Левенштейн Расстояние
Еще один очень хороший пример использования динамического программирования - это расстояние редактирования или расстояние Левенштейна .
Расстояние Левенштейна для двух строк A и B - это количество
атомарных операций, которые нам нужно использовать для преобразования
A в B а именно:
- Удаление персонажа
- Вставка символа
- Подстановка символов (технически это несколько операций, но для простоты назовем это атомарной операцией)
Эта проблема решается путем методичного решения проблемы для подстрок начальных строк, постепенно увеличивая размер подстрок, пока они не станут равными начальным строкам.
Рекуррентное соотношение, которое мы используем для этой задачи, выглядит следующим образом:
$$ lev_ {a, b} (i, j) = min \ begin {cases} lev_ {a, b} (i-1, j) +1 \\ lev_ {a, b} (i, j -1) +1 \\ lev_ {a, b} (i-1, j-1) + c (a_i, b_j) \ end {case} $$
c(a,b) равняется 0, если a==b , и 1, если a!=b .
Если вам интересно узнать больше о расстоянии Левенштейна, мы уже рассмотрели его на Python в другой статье: Расстояние Левенштейна и подобие текста в Python
Выполнение
public class editDistance {
public static void main(String[] args) {
String s1, s2;
Scanner scanner = new Scanner(System.in);
System.out.println("Insert first string:");
s1 = scanner.next();
System.out.println("Insert second string:");
s2 = scanner.next();
int n, m;
n = s1.length();
m = s2.length();
// Matrix of substring edit distances
// example: distance[a][b] is the edit distance
// of the first a letters of s1 and b letters of s2
int[][] distance = new int[n + 1][m + 1];
// Matrix initialization:
// If we want to turn any string into an empty string
// the fastest way no doubt is to just delete
// every letter individually.
// The same principle applies if we have to turn an empty string
// into a non empty string, we just add appropriate letters
// until the strings are equal.
for (int i = 0; i <= n; i++) {
distance[i][0] = i;
}
for (int j = 0; j <= n; j++) {
distance[0][j] = j;
}
// Variables for storing potential values of current edit distance
int e1, e2, e3, min;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
e1 = distance[i - 1][j] + 1;
e2 = distance[i][j - 1] + 1;
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
e3 = distance[i - 1][j - 1];
} else {
e3 = distance[i - 1][j - 1] + 1;
}
min = Math.min(e1, e2);
min = Math.min(min, e3);
distance[i][j] = min;
}
}
System.out.println("Edit distance of s1 and s2 is: " + distance[n][m]);
}
}
Выход :
Insert first string:
man
Insert second string:
machine
Edit distance of s1 and s2 is: 3
Самая длинная общая подпоследовательность (LCS)
Проблема заключается в следующем:
Для двух последовательностей найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность - это последовательность, которая появляется в том же относительном порядке, но не обязательно непрерывно.
Разъяснение
Если у нас есть две строки, s1 = "MICE" и s2 = "MINCE" , самой
длинной общей подстрокой будет «MI» или «CE», однако самой длинной
общей подпоследовательностью будет «MICE», потому что элементы
результирующей подпоследовательности не обязательно в последовательном
порядке.
Отношение повторения и общая логика
$$ lcs_ {a, b} (i, j) = min \ begin {cases} lcs_ {a, b} (i-1, j) \\ lcs_ {a, b} (i, j-1 ) \\ lcs_ {a, b} (i-1, j-1) + c (a_i, b_j) \ end {case} $$
Как видим, разница между расстоянием Левенштейна и LCS незначительна, а именно в стоимости ходов.
В LCS у нас нет затрат на вставку и удаление символов, что означает, что
мы учитываем только затраты на замену символов (диагональные
перемещения), стоимость которых равна 1, если два текущих строковых
символа a[i] и b[j] такие же.
Конечная стоимость LCS - это длина самой длинной подпоследовательности для двух строк, что нам и нужно.
Используя эту логику, мы можем свести множество алгоритмов сравнения строк к простым рекуррентным отношениям, которые используют базовую формулу расстояния Левенштейна.
Выполнение
public class LCS {
public static void main(String[] args) {
String s1 = new String("Hillfinger");
String s2 = new String("Hilfiger");
int n = s1.length();
int m = s2.length();
int[][] solutionMatrix = new int[n+1][m+1];
for (int i = 0; i < n; i++) {
solutionMatrix[i][0] = 0;
}
for (int i = 0; i < m; i++) {
solutionMatrix[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int max1, max2, max3;
max1 = solutionMatrix[i - 1][j];
max2 = solutionMatrix[i][j - 1];
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
max3 = solutionMatrix[i - 1][j - 1] + 1;
} else {
max3 = solutionMatrix[i - 1][j - 1];
}
int tmp = Math.max(max1, max2);
solutionMatrix[i][j] = Math.max(tmp, max3);
}
}
System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);
}
}
Выход :
Length of longest continuous subsequence: 8
Другие проблемы, связанные с динамическим программированием
Есть еще много проблем, которые можно решить с помощью динамического программирования, это лишь некоторые из них:
- Проблема с разделом ( скоро )
- Учитывая набор целых чисел, выясните, можно ли его разделить на два подмножества с равными суммами.
- Задача суммы подмножества ( скоро )
- Учитывая набор положительных целых чисел и сумму значений, определите, существует ли подмножество данного набора с суммой, равной данной сумме.
- Проблема со сменой монет (скоро появится общее количество способов узнать номинал монет)
- Учитывая неограниченный запас монет заданного достоинства, найдите общее количество различных способов получить желаемую сдачу.
- Общие возможные решения линейного уравнения
kпеременных ( скоро ) - Учитывая линейное уравнение
kпеременных, подсчитайте общее количество его возможных решений. - Найдите вероятность того, что пьяница не упадет со скалы ( дети, не пытайтесь делать это дома )
- Учитывая линейное пространство, представляющее расстояние от обрыва,
и при условии, что вы знаете начальное расстояние пьяницы от обрыва
и его склонность идти к обрыву
pи от обрыва1-p, вычислите вероятность его выживания. - Многое другое...
Заключение
Динамическое программирование - это инструмент, который может сэкономить нам много вычислительного времени в обмен на большую сложность пространства, при условии , что некоторые из них идут только наполовину (матрица необходима для мемоизации, но используется постоянно меняющийся массив).
Это сильно зависит от типа системы, над которой вы работаете, если время ЦП дорого, вы выбираете решение, потребляющее память, с другой стороны, если ваша память ограничена, вы выбираете более трудоемкое решение для лучшее соотношение времени и пространства.