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

1. Введение

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

Чтобы понять концепцию динамического программирования, нам необходимо ознакомиться с несколькими темами:

1. Что такое динамическое программирование?
2. как дела
3. Упрощенная задача о рюкзаке
4. традиционная задача о рюкзаке
5. Levenshtein Distance
6. LCS — самая длинная общая подпоследовательность
7. Другие проблемы с использованием динамического программирования
8. в заключении

Все коды в этой статьеjavaКод.

2. Что такое динамическое программирование?

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

Чтобы понять динамическое программирование, нам сначала нужно понять проблему отношений рекурсии. Каждая отдельная сложная проблема может быть разделена на небольшие подзадачи, а это значит, что мы можем построить рекурсивную связь между этими проблемами. Рассмотрим знакомый пример:Последовательность Фибоначчи, определение последовательности Фибоначчи имеет следующее рекуррентное соотношение:

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

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

Однако каждый раз, когда мы хотим вычислитьFibonacciПри разных элементах последовательности у нас есть несколько повторяющихся вызовов, при рекурсивном вызове, как показано на рисунке ниже, мы вычисляемFibonacci（5）:

Например: если мы хотим вычислитьF(5), очевидно, нам нужно вычислитьF(3)иF(4)как расчетF(5)предпосылки. Однако для расчетаF(4), нам нужно вычислитьF(3)иF(2), поэтому нам нужно вычислитьF(2)иF(1)получитьF(3), другие решения и так далее.

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

При таком подходе мы моделируем решение так, как будто собираемся решать его рекурсивно, но решаем его с нуля, запоминая решение подзадач (подшагов), предпринятых для достижения вершины. Следовательно, дляFibonacciпоследовательность, сначала решаем и запоминаемF（1）иF（2）, а затем вычислить, используя два шага памятиF（3）,Так далее и тому подобное. Это означает, что вычисление для каждого отдельного элемента в последовательностиO（1）, так как мы уже знаем первые два элемента.

При использовании динамического программирования для решения проблемы мы обычно используем следующие три шага:

1. Определение применимо к проблеме рекурсивных отношений
2. Начальное значение памяти инициализации, массив, матрица
3. Убедитесь, что он всегда разрешается заранее, когда мы делаем рекурсивные вызовы (с доступом к ответам на подзадачи).

Следуя этим правилам, рассмотрим пример алгоритма с использованием динамического программирования:

3. Жадный алгоритм

Возьмем это в качестве примера:

Given a rod of length n and an array that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

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

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

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

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

3.2 Динамические методы

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

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 значениями. Для выполнения алгоритма требуется около 5,2 секунды, а для выполнения динамического решения требуется около 0,000095 секунды.

4. Упрощенная задача о рюкзаке

Упрощенная задача о рюкзаке — это оптимизационная задача, не имеющая единого решения. Вопрос этого вопроса - "Существует ли решение?":

Given a set of items, each with a weight w1, w2... determine the number of each item to put in a knapsack so that the total weight is less than or equal to a given limit K.

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

Сначала давайте сохраним все веса элементов в массиве W. Далее предположим, что естьnэлементы, нумеруем их числами от 1 до n, поэтому первыйiВес каждого предметаW [i]. мы сформируем（n + 1）x（K + 1）размерная матрицаM.M [x] [y]соответствует решению задачи о рюкзаке, но включает только первую часть исходного массиваxпредметов, а максимальная вместимость составляетy

Например

Предположим, у нас есть 3 элемента, веса равныw1=2kg,w2=3kg,w3=4kg. Используя описанный выше метод, мы можем сказатьM [1] [2]является допустимым решением. Это означает, что мы пытаемся использовать первый элемент в массиве весов (w1) для рюкзака вместимостью 2 кг.

существуетM [3] [5], мы пытаемся использовать первые 3 элемента массива весов（w1，w2，w3）Рюкзак вместимостью 5 кг. Это неэффективное решение, потому что мы его переоснащаем.

4.1 Инициализация матрицы

При инициализации матриц следует помнить о двух вещах:

Does a solution exist for the given subproblem (M[x][y].exists) AND does the given solution include the latest item added to the array (M[x][y].includes).

Существует ли решение данной подзадачи (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, но для каждогоkзаM[k][0].includes = false.

Примечание: только потому, что для данногоM [x] [y]Решение существует, это не обязательно означает, что данная конкретная комбинация является решением. существуетM [10] [0]В случае существует решение, не включающее ни один из 10 элементов. ЭтоM [10] [0] .exists = trueноM [10] [0] .includes = falseпричина.

4.2 Алгоритмические принципы

Далее, давайте построим, используя следующий псевдокодM [i] [k]Рекуррентное отношение:

if (M[i-1][k].exists == True):  
    M[i][k].exists = True
    M[i][k].includes = False
elif (k-W[i]>=0):  
    if(M[i-1][k-W[i]].exists == true):
        M[i][k].exists = True
        M[i][k].includes = True
else:  
    M[i][k].exists = False

Таким образом, суть раствора состоит в том, чтобы разделить подгруппу в два случая:

1. для емкостиk, когда есть первыйi-1решение элемента
2. для емкостиk-W [i], когда первыйi-1Элемент существует решение

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

Второй случай относится к знанию первогоi-1элемент решения, но емкость не заполнена только одним i-м элементом, а значит, мы можем добавить i-й элементiэлементы, и у нас есть новое решение!

4.3. Реализация

Какая реализация ниже упрощает задачу, мы создали класс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);
    }
}

5. Традиционная задача о рюкзаке

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

Given a set of items, each with a weight w1, w2... and a value v1, v2... determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit k and the total value is as large as possible.

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

В реализации будем использовать старый класс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  

6. Levenshtein Distance

Еще один очень хороший пример использования динамического программирования:Edit DistanceилиLevenshtein Distance.

Levenshtein Distanceэто две строкиA,B, нам нужно использовать атомарные операции дляAпреобразовать вB:

1. строка удалить
2. Вставка строки
3. замена символов (технически это более чем одна операция, но для простоты мы будем называть ее атомарной операцией)

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

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

еслиa == bноc（a，b）равно 0, еслиa = = bноc（a，b）1.

выполнить:

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  

Если вы хотите узнать больше оLevenshtein DistanceРешение, которое мы использовали в другой статьеpythonДостигнутоLevenshtein Distance and Text Similarity in Python, Используя эту логику, мы можем свести многие алгоритмы сравнения строк к простому рекурсивному отношению, в котором используетсяLevenshtein DistanceОсновная формула

7. Самая длинная общая подпоследовательность (LCS)

Проблема описана следующим образом:

Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

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

Прозрачный:

Если у нас есть две строкиs1="MICE"иs2="MINCE", самая длинная общая подпоследовательностьMIилиCE. Однако самая длинная общая подпоследовательность будет «MICE», потому что элементы результирующей подпоследовательности не обязательно должны быть в последовательном порядке.

Отношение рекурсии и общая логика:

Мы видим, что,Levenshtein distanceиLCSЕсть только небольшая разница, особенно стоимость переезда.

существуетLCS, у нас нет затрат на вставку и удаление символов, что означает, что мы вычисляем стоимость замены символов (диагонального смещения), только если два текущих символа строкиa [i]иb [j]одинаковые, стоимость 1.

LCSКонечная стоимость — это длина самой длинной подпоследовательности из 2 строк, что нам и нужно.

Using this logic, we can boil down a lot of string comparison algorithms to simple recurrence relations which utilize the base formula of the Levenshtein distance

Используя эту логику, мы можем свести многие алгоритмы сравнения строк к простому рекурсивному отношению, в котором используетсяLevenshtein distanceосновная формула.

выполнить:

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  

8. Другие проблемы с использованием динамического программирования

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

1. Задача о разбиении: задан набор целых чисел, выясните, можно ли его разделить на два подмножества с равными суммами.
2. Проблема суммы подмножества: Дан массив положительных целых чисел и элементов и общее значение, есть ли подмножество элементов в массиве и сумма элементов равна общему значению.
3. Задача о вариациях монет: учитывая бесконечное количество монет заданного номинала, найдите общее количество различных способов получить желаемую вариацию.
4. Все возможные решения линейного уравнения с k переменными. Для заданного линейного уравнения с k переменными подсчитайте общее количество возможных его решений.
5. Найдите вероятность того, что пьяный не упадет с обрыва: задано линейное пространство, представляющее расстояние от обрыва, сообщите, как далеко пьяный стартует от обрыва, и его склонность направиться к обрыву p и от обрыва 1-р, Рассчитайте его вероятность выживания

9. Заключение

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

оригинал:стек abuse.com/dynamic-pro…

Автор: Владимир Баточанин

Переводчик: ли