У цьому підручнику ви дізнаєтесь, що таке динамічне програмування. Крім того, ви знайдете порівняння між динамічним програмуванням та жадібними алгоритмами вирішення проблем.
Динамічне програмування - це техніка комп’ютерного програмування, яка допомагає ефективно вирішувати клас проблем, що мають перекриваються підзадачі та оптимальну властивість підструктури.
Такі проблеми передбачають неодноразове обчислення значення одних і тих же підзадач для пошуку оптимального рішення.
Приклад динамічного програмування
Візьмемо випадок генерації послідовності Фібоначчі.
Якщо послідовність 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) функція fib (n), якщо клавіша n відсутня в map mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Динамічне програмування за допомогою мемоїзування - це підхід зверху вниз до динамічного програмування. Змінивши напрямок, в якому працює алгоритм, тобто, починаючи з базового випадку та працюючи до рішення, ми також можемо реалізувати динамічне програмування знизу вгору.
функція fib (n), якщо n = 0 повертає 0 ще var prevFib = 0, currFib = 1 повторює n - 1 раз var newFib = prevFib + currFib prevFib = currFib currFib = newFib повертає струмFib
Рекурсія проти динамічного програмування
Динамічне програмування в основному застосовується до рекурсивних алгоритмів. Це не випадково, більшість проблем оптимізації вимагають рекурсії, а для оптимізації використовується динамічне програмування.
Але не всі проблеми, що використовують рекурсію, можуть використовувати динамічне програмування. Якщо не існує перекриваються підзадач, як у задачі послідовності Фібоначчі, рекурсія може досягти рішення лише за допомогою підходу розділити та завоювати.
Саме тому рекурсивний алгоритм, такий як Merge Sort, не може використовувати динамічне програмування, оскільки підзадачі жодним чином не перекриваються.
Жадібні алгоритми проти динамічного програмування
Жадібні алгоритми схожі на динамічне програмування в тому сенсі, що обидва вони є інструментами для оптимізації.
Однак жадібні алгоритми шукають оптимальні для місцевості рішення або, іншими словами, жадібний вибір, в надії знайти загальний оптимум. Отже, жадібні алгоритми можуть зробити припущення, яке на той час виглядає оптимальним, але стає дорогим і не гарантує глобального оптимуму.
З іншого боку, динамічне програмування знаходить оптимальне рішення підзадач, а потім робить обгрунтований вибір, поєднуючи результати цих підпроблем, щоб знайти найбільш оптимальне рішення.
