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

Опубликовано: 2021-02-08

Оглавление

Введение

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

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

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

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

Динамическое программирование имеет две концепции:

  1. Перекрывающиеся подзадачи
  2. Оптимальная основа

Перекрывающиеся подзадачи

Классическим примером понимания концепции перекрывающихся подзадач является программа для печати рядов Фибоначчи.

Логика ряда Фибоначчи задается как «фибоначчи (n) = фибоначчи (n-1) + фибоначчи (n-2)». И беспрепятственно выполнить эту функцию можно с помощью рекурсивного решения с базовым случаем фибоначчи (0) = 0 и фибоначчи (1) = 1.

общедоступный статический интервал Фибоначчи (int n) {
 если (n== 0 || n== 1 )
 вернуть н;
 вернуть фибоначчи (n -1 ) + фибоначчи (n -2 );
 }
 public static void main(String[] args){
 System.out.print( "Четвертое число Фибоначчи" +fibonacci( 4 ));
 }

Скажем, нам нужно напечатать 4-ю цифру Фибоначчи, тогда дерево рекурсии выглядит как

Фибоначчи(4)

/ \

Фибоначчи (3) + Фибоначчи (2)

/ \ / \

Фибоначчи(2) + Фибоначчи(1) Фибоначчи(1) + Фибоначчи(0)

/ \

Фибоначчи (1) + Фибоначчи (0)

Обратите внимание, что число Фибоначчи (4) является 5-й цифрой в ряду Фибоначчи, потому что мы начинаем с числа Фибоначчи (0). В приведенном выше дереве рекурсии мы видим, что fibonacci(2) повторяется дважды. Мы наблюдали дублирование в дереве рекурсии высотой 4, теперь представьте, что у нас есть рекурсивный вызов огромного числа, а впоследствии будет дерево рекурсии с большой высотой. И будет много таких повторяющихся вычислений, которые известны как перекрывающиеся подзадачи.

У нас есть два метода работы с этим (i) табулированием, (ii) запоминанием.

Давайте разберемся с ними, пройдясь по их реализациям.

Мемоизация

Решение задачи Фибоначчи с помощью метода запоминания можно выполнить, как показано ниже.

статическая памятка int[];
общедоступный статический интервал Фибоначчи (int n) {
если(памятка[n]!=-1)
вернуть памятку[n];
если(n==0 || n==1){
памятка[n]=n;
вернуть н;
}
памятка [n] = фибоначчи (n-1) + фибоначчи (n-2);
вернуть памятку[n];
}
public static void main(String[] args){
памятка = новый интервал [5];
для (целое я = 0; я <= 4; я ++)
памятка[i]=-1;
System.out.println("4-е число Фибоначчи равно "+Fibonacci(4));
}

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

Вся логика аналогична рекурсивному решению, но единственная разница, которую мы сделали, заключается в том, что мы отмечаем их в массиве memo, прежде чем возвращать значение основному методу. Единственным ограничением этого алгоритма является то, что нам нужно дополнительное пространство размером O(n), но мы оптимизируем предыдущее рекурсивное решение.

Табулирование

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

общедоступный статический интервал Фибоначчи (int n) {
 int table[]=new int[n+ 1 ];
 для (целое я = 0 ; я <= п; я ++) {
 если (я== 0 || я== 1 )
 таблица[я]=я;
 еще {
 таблица[i]=таблица[i -1 ]+таблица[i -2 ];
 }
 }
 вернуть таблицу[n];
 }
 public static void main(String[] args){
 System.out.println( "Четвертое число Фибоначчи" +fibonacci( 4 ));
 }

Поскольку мы знаем, что fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), в мемоизации мы начали с вызова функции fibonacci(4), а затем поняли, что не вычислили ее значение, поэтому мы вычислили его значения, а затем сохранили их.

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

У нас также есть способ итеративно вычислять числа Фибоначчи от 0 до n-го элемента, а затем возвращать n-й элемент Фибоначчи. Это то, что мы реализовали в приведенном выше коде. Этот код также требует того же места O (n).

Checkout: Навыки, чтобы стать разработчиком полного стека

Оптимальная основа

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

И классический пример этой концепции — рассмотрение обхода между узлами в графе.

Предположим, что у нас есть несколько корней из Теланганы в Дели. И если у нас есть кратчайший маршрут, который проходит через Нагпур и Гвалиор. Тогда кратчайший путь из Нагпура в Дели-Дели должен пройти через Гвалиор. Теперь мы можем разделить нашу проблему на подзадачи: от Теланганы до Нагпура, от Нагпура до Гвалиора, от Гвалиора до Дели.

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

Таким образом, идея состоит в том, чтобы решить ее путем оптимального решения ее подзадач. Пусть n будет длиной самой длинной общей подпоследовательности.

Если n=LCS(картошка, татуировка), то n=LCS(картошка,tatto)+1 (если последние символы совпадают), иначе n=maximum(LCS(картошка,tatto), LCS(картошка, татуировка).

статический int lcs (строка s1, строка s2, int m, int n) {
 int dp[][] = new int[m+ 1 ][n+ 1 ];
 для (целое я = 0 ; я <= м; я ++) {
 для (int j = 0 ; j <= n; j++) {
 если (я == 0 || j == 0 )
 дп[я][j] = 0 ;
 иначе если (s1.charAt(i - 1 ) == s2.charAt(j- 1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 еще
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 вернуть дп[м][п];
 }
 public static void main(String[] args){
 System.out.println( "Нога самой длинной общей подпоследовательности" +lcs( "картошка" , "татуировка" , 6 , 6 ));
 }

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

Читайте также: Зарплата Full Stack Developer в Индии

Изучайте онлайн -курсы по разработке программного обеспечения в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Заключение

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

В заключение, курсы Full Stack Developers — это высококвалифицированные специалисты, которые могут справиться со всем, что связано с веб-разработкой. Эти навыки Full Stack Developer отличают их от Frontend и Backend разработчиков.

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

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

Что такое перекрывающаяся подзадача в динамическом программировании?

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

Какова оптимальная подструктура в динамическом программировании?

Оптимальная подструктура подразумевает, что оптимальное решение проблемы связано с оптимальным решением меньшей задачи в рамках того же определения задачи. Оптимальная подструктура — это дополнительное требование, необходимое для решения задач или для доказательства отсутствия решения. С оптимальной подструктурой мы можем доказать NP-трудность многих задач. Общий подход к решению задач DP заключается в использовании матрицы динамического программирования для хранения оптимального решения подзадач. Матрица динамического программирования может использоваться для решения любых ненулевых задач оптимальной подструктуры DP.