В этом руководстве вы узнаете, что такое динамическое программирование. Кроме того, вы найдете сравнение между динамическим программированием и жадными алгоритмами решения проблем.
Динамическое программирование - это метод компьютерного программирования, который помогает эффективно решать класс задач, которые имеют перекрывающиеся подзадачи и свойство оптимальной подструктуры.
Такие задачи включают многократное вычисление значения одних и тех же подзадач для поиска оптимального решения.
Пример динамического программирования
Возьмем случай генерации последовательности Фибоначчи.
Если последовательность F (1) F (2) F (3)… F (50), она следует правилу F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Обратите внимание, как есть перекрывающиеся подзадачи, нам нужно вычислить F (48), чтобы вычислить как F (50), так и F (49). Именно в этом алгоритме динамическое программирование сияет.
Как работает динамическое программирование
Динамическое программирование работает, сохраняя результаты подзадач, так что, когда их решения требуются, они всегда под рукой, и нам не нужно их пересчитывать.
Этот метод сохранения значения подзадач называется мемоизацией. Сохраняя значения в массиве, мы экономим время на вычислениях подзадач, с которыми мы уже столкнулись.
var m = map (0 → 0, 1 → 1) function fib (n), если ключ n отсутствует в map mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Динамическое программирование с помощью мемоизации - это нисходящий подход к динамическому программированию. Изменив направление, в котором работает алгоритм, т. Е. Начав с базового случая и работая в направлении решения, мы также можем реализовать динамическое программирование по восходящей схеме.
функция fib (n) if n = 0 return 0 else var prevFib = 0, currFib = 1 повторение n - 1 раз var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Рекурсия против динамического программирования
Динамическое программирование в основном применяется к рекурсивным алгоритмам. Это не случайно, большинство задач оптимизации требуют рекурсии, а для оптимизации используется динамическое программирование.
Но не все задачи, использующие рекурсию, могут использовать динамическое программирование. Если нет перекрывающихся подзадач, как в проблеме последовательности Фибоначчи, рекурсия может достичь решения только с использованием подхода «разделяй и властвуй».
По этой причине рекурсивный алгоритм, такой как сортировка слиянием, не может использовать динамическое программирование, поскольку подзадачи никоим образом не перекрываются.
Жадные алгоритмы против динамического программирования
Жадные алгоритмы похожи на динамическое программирование в том смысле, что они оба являются инструментами оптимизации.
Однако жадные алгоритмы ищут локально оптимальные решения или, другими словами, жадный выбор в надежде найти глобальный оптимум. Следовательно, жадные алгоритмы могут сделать предположение, которое в данный момент выглядит оптимальным, но в дальнейшем становится дорогостоящим и не гарантирует глобального оптимума.
С другой стороны, динамическое программирование находит оптимальное решение подзадач, а затем делает осознанный выбор для объединения результатов этих подзадач, чтобы найти наиболее оптимальное решение.
