Решение проблем — задача оптимизации

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

Все, что нам нужно знать о динамическом программировании

Привет народ 👋,

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

Знаете ли вы о проблеме с оптимизацией?

  • Задача нахождения оптимального решения из всех возможных вариантов известна как задача оптимизации.
  • например, Предположим, Вам нужно отправиться в Петту из Моратувы. Ваша цель — найти экономичное решение. Между этими двумя местами есть два маршрута, такие как маршрутный автобус Галле и маршрутный автобус Моратува. Но автобус по маршруту Галле стоит дороже, чем маршрут по Моратуве. Оба они являются возможными решениями. Тем не менее, маршрут Моратува является оптимальным решением, исходя из нашей цели. Это проблема оптимизации.

Знаете ли вы о рекурсии при решении задач?

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

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

Динамическое программирование (DP) — это алгоритмический метод решения задачи оптимизации путем ее разбиения на более мелкие подзадачи и использования того факта, что лучшее решение общей проблемы определяется лучшим решением ее подзадач. Когда я скажу это, ваш мозг вдруг подумает: Ой, подождите, это же «рекурсия, верно😳?» Но ответа нет. Давайте посмотрим, как они отличаются.

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

# Fibonacci Series by Resursive Approach
def fib(n): 
    if (n == 0):
      return 0 
    if (n == 1):
      return 1 
    return fibo(n-1) + fibo(n-2)
# Fibonacci Series by DP Approach
def fib(n):
    return fiboRec(n, new int[n+1])
def fiboRec(n,memo):
    if (n == 0)
       return 0
    if (n == 1): 
       return 1
    if (memo[n] == 0): 
       memo[n] = fibRec(n-1, memo) + fibRec(n-2, memo)
    return memo[n]

Давайте найдем фибо(5).

В рекурсивном подходе

Я покажу звонки соответственно

  • выдумка(5) = › выдумка(4), выдумка(3)
  • выдумка(4) => выдумка(3), выдумка(2)
  • выдумка(3) => выдумка(2),выдумка(1)
  • выдумка(3) => выдумка(2),выдумка(1)
  • выдумка(2) => выдумка(1), выдумка(0)
  • выдумка(2) => выдумка(1), выдумка(0)
  • выдумка(1) => 1
  • выдумка(2) => выдумка(1), выдумка(0)
  • выдумка(1) => 1
  • выдумка(1) => 1
  • выдумка(0) => 1
  • выдумка(1) => 1
  • выдумка(0) => 1
  • выдумка(1) => 1
  • выдумка(0) => 1

Там будет столько рекурсивных вызовов. Вы можете видеть, что fib(3) и fib(2) вызываются снова и снова. Он также рассчитывается снова и снова. Это неэффективный способ сделать это.

В подходе DP

  • выдумка(5) = › выдумка(4), выдумка(3)
  • выдумка(4) => выдумка(3), выдумка(2)
  • выдумка(3) => выдумка(2),выдумка(1)
  • выдумка(2) => выдумка(1), выдумка(0)
  • выдумка(1) => 1
  • выдумка(0) => 1

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

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

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

Решение проблем с помощью динамического программирования

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

  1. Сверху вниз с запоминанием
  2. Подход "снизу вверх" с табулированием

Сверху вниз с запоминанием

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

Восходящий подход с табулированием

В отличие от метода «сверху вниз», табулирование позволяет избежать повторения. В этом методе мы решаем проблему «снизу вверх» (т. е. сначала решая все связанные подзадачи, сортируя размер проблемы). Обычно это достигается путем заполнения n-мерной таблицы. Затем на основе результатов таблицы вычисляется ответ на главную/исходную задачу.

Приведенное ниже видео поможет понять дальнейшие подходы «сверху вниз» и «снизу вверх» в динамическом программировании.

Многие задачи решаются с помощью динамического программирования для понимания целей, таких как задача о рюкзаке 0/1, задача умножения цепочек матриц, задача разрезания стержня и т. д. Вы можете легко найти эти решения в Интернете. Решения этих проблем помогут очень четко прояснить концепцию динамического программирования.

Жадный подход

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

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

Понравилась статья? Станьте участником Medium, чтобы продолжать обучение без каких-либо ограничений. Я получу часть вашего членского взноса, если вы воспользуетесь приведенной выше ссылкой, без каких-либо дополнительных затрат для вас. Заранее спасибо.