mafulechka
2 августа 2019 г. 14:28

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

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

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


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

Возьмем случай генерации последовательности Фибоначчи .

Если последовательность 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). Это именно тот алгоритм, где хорошо виден пример динамического программирования.

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

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

Эта техника хранения значения подзадач называется мемоизацией (запоминанием) . Сохраняя значения в массиве, мы экономим время для вычислений подзадач, с которыми мы уже сталкивались.

  1. var m = map(0 0, 1 1)
  2. function fib(n)
  3. if key n is not in map m
  4. m[n] = fib(n 1) + fib(n 2)
  5. return m[n]

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

  1. function fib(n)
  2. if n = 0
  3. return 0
  4. else
  5. var prevFib = 0, currFib = 1
  6. repeat n 1 times
  7. var newFib = prevFib + currFib
  8. prevFib = currFib
  9. currFib = newFib
  10. return currentFib

Рекурсия vs Динамического программирования

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

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

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

Жадные алгоритмы vs Динамического программирования

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

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

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

Вам это нравится? Поделитесь в социальных сетях!

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь