Рубрики
Без рубрики

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

Автор оригинала: Vladimir Batoćanin.

Вступление

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

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

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

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

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

$$ (n-1)+фибоначчи(n-2) $$

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

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

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

Например, если мы хотим вычислить 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 значениями.

Наивное решение заняло ~5,2 с для выполнения, в то время как динамическое решение заняло ~0,000095 с для выполнения.

Упрощенная проблема С Рюкзаком

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

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

Итак, давайте сделаем шаг назад и выясним, как мы будем представлять решения этой проблемы. Во-первых, давайте сохраним веса всех элементов в массиве W .

Далее, предположим , что есть n предметов, и мы перечислим их числами от 1 до n , поэтому вес i-го предмета равен W[i] .

Мы сформируем матрицу M из (n+1) x (K+1) измерений. M[x][y] соответствует решению проблемы рюкзака, но включает только первые x элементы начального массива и с максимальной емкостью y .

Пример

Допустим, у нас есть 3 предмета, вес которых w1=2 кг , w2=3 кг и w3=4 кг .

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

Находясь в M[3][5] мы пытаемся наполнить рюкзак вместимостью 5 кг, используя первый 3 элементы массива весов ( w1,w2,w3 ). Это неправильное решение, так как мы его переоцениваем.

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

При заполнении матрицы необходимо отметить 2 вещи:

Существует ли решение для данной подзадачи (M[x][y].существует) И включает ли данное решение последний элемент, добавленный в массив (M[x][y].включает).

Поэтому инициализация матрицы довольно проста, M[0][k].существует всегда ложно , если k > 0 , потому что мы не клали никаких предметов в рюкзак с k емкостью.

С другой стороны, M[0][0].существует , потому что рюкзак должен быть пустым с самого начала , так как k , и поэтому мы не можем ничего положить, и это правильное решение.

Кроме того, мы можем сказать, что M[k][0].существует , но также M[k][0].включает для каждого k .

Git Essentials

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

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

Принцип алгоритма

Далее, давайте построим рекуррентное соотношение для 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. Когда решение существует для первых i-1 элементов, для емкости k
  2. Когда решение существует для первых i-1 элементов, но для емкости k-W[i]

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

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

Реализация

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

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 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 , а общая стоимость была как можно больше.

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

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

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

Расстояние Левенштейна

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

Расстояние Левенштейна для 2 строк A и B – это количество атомарных операций, которые нам нужно использовать для преобразования A в B , которые являются:

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

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

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

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 и s2 , самой длинной общей подстрокой будет “MI” или “CE”, однако самой длинной общей подпоследовательностью будет “МЫШИ”, потому что элементы результирующей подпоследовательности не обязательно должны быть в последовательном порядке.

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

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

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

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

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

Реализация

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 , рассчитайте вероятность его выживания.
  • Гораздо больше…

Вывод

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

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

Читайте ещё по теме: