ЖАДНЫЙ ПОДХОД против ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

Есть два необходимых условия, которым должна удовлетворять задача, чтобы DP работала.

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

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

Сверху вниз:

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

Запомнить != запомнить

Снизу вверх:

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

Понимание динамического программирования на примерах

Начнем с простого примера ряда Фибоначчи.

Ряд Фибоначчи – это последовательность чисел, в которой каждое число является суммой двух предыдущих, начиная с 0 и 1.

F(n) = F(n-1) + F(n-2)

Рекурсивный метод:

def r_fibo(n):
   if n <= 1:
       return n
   else:
       return(r_fibo(n-1) + r_fibo(n-2))

Здесь программа снова и снова будет вызывать себя для вычисления дальнейших значений. Расчет временной сложности подхода, основанного на рекурсии, составляет около O(2^N). Пространственная сложность этого подхода составляет O (N), поскольку рекурсия может достигать N.

Например-

F(4) = F(3) + F(2) = ((F(2) + F(1)) + F(2) = ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

В этом методе такие значения, как F(2), вычисляются дважды, а вызовы F(1) и F(0) выполняются несколько раз. Представьте себе количество повторений, если вам нужно вычислить его F (100). Этот методнеэффективен для больших значений.

Метод сверху вниз

def fibo(n, memo):
  if memo[n] != null:
    return memo[n]
  if n <= 1:
    return n
  else:
    res = fibo(n-1) + fibo(n+1)
    memo[n] = res
    return res

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

Снизу вниз

def fib(n):
  if n<=1:
    return n
  list_ = [0]*(n+1)
  list_[0] = 0
  list_[1] = 1 
  for i in range(2, n+1):
    list_[i] = list_[i-1] + list[i-2]
  return list_[n]

Этот код вообще не использует рекурсию. Здесь мы создаем пустой список длины (n+1) и устанавливаем базовый случай F(0) и F(1) в позиции индекса 0 и 1. Этот список создается для хранения соответствующих вычисленных значений с использованием цикла for. для значений индекса от 2 до n.

В отличие от рекурсивного метода временная сложность этого кода является линейной и требует гораздо меньше времени для вычисления решения, так как цикл выполняется от 2 до n, т. е. выполняется за O( п). Этот подход является наиболее эффективным способом написания программы.

Временная сложность: O(n) ‹‹‹ O(2^N)

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

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

Алгоритм никогда не отменяет предыдущее решение, даже если выбор неверен. Он работает по принципу «сверху вниз».

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

Компоненты жадного алгоритма

Компоненты, которые можно использовать в жадном алгоритме:

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

Приложения жадного алгоритма

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

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

Подсчет монет

Эта проблема заключается в подсчете до желаемого значения путем выбора наименьшего возможного количества монет, а жадный подход заставляет алгоритм выбирать максимально возможную монету. Если нам предоставят монеты номиналом 1, 2, 5 и 10 фунтов стерлингов и нас попросят посчитать 18 фунтов стерлингов, то жадная процедура будет такой:

1 — выберите одну монету номиналом 10 ₹, оставшееся количество равно 8.
2 — затем выберите одну монету ₹ 5, оставшееся количество равно 3
3 — затем выберите одну монету ₹ 2, оставшееся количество равно 1.
4 — И, наконец, выбор одной монеты ₹ 1 решает проблему

Хотя вроде работает нормально, для этого подсчета нам нужно подобрать всего 4 монеты. Но если мы немного изменим задачу, то тот же подход может не дать такого же оптимального результата.

Для валютной системы, где у нас есть монеты достоинством 1, 7, 10, подсчет монет достоинством 18 будет абсолютно оптимальным, но для счета вроде 15 может понадобиться больше монет, чем необходимо. Например, жадный подход будет использовать 10 + 1 + 1 + 1 + 1 + 1, всего 6 монет. В то время как ту же проблему можно решить, используя всего 3 монеты (7 + 7 + 1).

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

Разница между динамическим программированием и жадным подходом

Заключение

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

ЖАДНЫЙ ПОДХОД против ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

ЖАДНЫЙ ПОДХОД против ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

Сверху вниз:

Снизу вверх:

Понимание динамического программирования на примерах

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

Компоненты жадного алгоритма

Приложения жадного алгоритма

Подсчет монет

Разница между динамическим программированием и жадным подходом

Заключение

Рекомендации

Вопросы по теме