Якщо ви коли-небудь стикалися із завданнями, де потрібно визначити найкраще рішення на основі певного набору обмежень, то ви, ймовірно, знаєте, що існує для цього метод динамічного програмування. Це досить потужний апарат, і за його допомогою можна розв’язувати задачі різної складності, від пошуку найбільшої загальної підпослідовності до визначення найвигіднішої комбінації товарів для рюкзака. Якщо ви хочете навчитися застосовувати цей метод, то вам необхідно розуміти, як працює апарат динамічного програмування. Усі ці питання ми розглянемо в цьому матеріалі.
Поняття “динамічне програмування” придумав і назвав 1940 року Річард Беллман, а змінив і доповнив його визначення – 1953 року. Беллману довелося багато часу витратити на вибір назви, бо його бос не любив математичні терміни. Тому автор визначення вибрав слово “програмування” замість “планування” і слово “динамічне”, щоб уникнути принизливих і лайливих тлумачень з боку керівника. Ось так було сформовано назву “динамічне програмування”.
Метод динамічного програмування (ДП) є одним з основних інструментів оптимізації та розв’язання задач в інформатиці, економіці, біології та інших галузях. Простими словами, динамічне програмування – це метод розв’язання задач, що ґрунтується на розбитті складної задачі на безліч дрібніших;
Важливо враховувати такі моменти:
За допомогою ДП ефективно розв’язують задачі з оптимізації, наприклад, якщо потрібно знайти найбільше або найменше значення функції. ДП також активно застосовується в задачах планування, де потрібно визначити оптимальну послідовність дій.
Давайте розберемося детальніше в основних поняттях методу.
Наприклад, нехай у нас є задача про знаходження найбільшої загальної підпослідовності двох рядків. Ми можемо розв’язувати її методом динамічного програмування, розбивши її на більш дрібні підзадачі – знаходження загальної підпослідовності для підрядків кожного з рядків. У цьому разі ми стикаємося з підзадачами, що перекриваються, – загальна підпослідовність для деяких підрядків уже може бути розрахована раніше і збережена в пам’яті. Таким чином, ми можемо уникнути повторних обчислень і розв’язати задачу більш ефективно.
ДП – це методологія розв’язання задач, яка являє собою не просто формулу або алгоритм, це скоріше роздуми про те, як розв’язати задачу.
Алгоритм методу динамічного програмування складається з кількох кроків:
Алгоритм методу ДП може бути застосований до широкого спектра задач, включно із задачами знаходження найкоротшого шляху в графі, оптимального розкладу робіт, знаходження максимального потоку в мережі та інші. Він має низку переваг, але також має недоліки і вимагає досить великого обсягу пам’яті для зберігання результатів підзадач.
Розглянемо два приклади застосування цієї техніки програмування.
Одним із найвідоміших прикладів використання методу динамічного програмування може бути розрахунок чисел Фібоначчі. Для обчислення будь-якого числа в послідовності нам необхідно спочатку обчислити два попередніх числа і скласти їх. Таким чином, для обчислення кожного наступного числа ми використовуємо результати попередніх обчислень. Хоча для обчислення чисел Фібоначчі є і замкнута формула.
Нехай у вас є набір чисел, і вам потрібно знайти максимальну суму, яку можна отримати, вибравши деякі з них, за умови, що вибрані числа не повинні стояти поруч одне з одним. Наприклад, для набору чисел [1, 2, 3, 1] максимальна сума дорівнює 4 (виберіть числа 1 і 3).
Це може здатися складним, але такий підхід дає змогу розв’язувати задачі в оптимальний спосіб і часто використовується в алгоритмах оброблення зображень, оброблення природної мови, ігрових додатках та інших галузях.
Візьмемо практичний приклад мовою Python:
def max_sum_sequence(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
# Обчислюємо максимальну суму для кожного елемента
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# Повертаємо максимальну суму для останнього елемента
return dp[-1]
Функція max_sum_sequence приймає список nums, що містить числа, і повертає максимальну суму підпослідовності. Спочатку ми перевіряємо довжину списку, якщо він порожній, то повертаємо 0, а якщо він містить тільки один елемент, то повертаємо його значення. Потім ми створюємо масив dp, в якому будемо зберігати максимальну суму для кожного елемента списку. Для першого елемента максимальна сума дорівнює самому елементу, а для другого елемента максимальна сума дорівнює максимальному значенню з двох перших елементів. Далі ми перебираємо елементи списку, що залишилися, і для кожного елемента обчислюємо максимальну суму, яку можна отримати, якщо вибрати елементи тільки з цього елемента і всіх елементів, що передують йому, але не з його сусідів. Для цього ми використовуємо формулу dp[i] = max(dp[i-1], dp[i-2] + nums[i]), де dp[i-1] – максимальна сума до попереднього елемента, а dp[i-2] + nums[i] – максимальна сума до поточного елемента, якщо ми не вибрали попередній елемент. Нарешті, ми повертаємо максимальну суму для останнього елемента списку, що і дає нам відповідь на вихідну задачу.
Ще одним прикладом використання методу ДП може бути розрахунок вартості рюкзака;
Припустімо, у вас є рюкзак і набір предметів із певними вагами та вартостями. Вам потрібно заповнити рюкзак таким чином, щоб максимізувати вартість обраних предметів, не перевищуючи місткість рюкзака.
Для розв’язання цієї задачі ми можемо використовувати таблицю заповнення. У кожній комірці таблиці зберігатиметься максимальна вартість, яку ми можемо отримати, використовуючи тільки перші i предметів і маючи рюкзак місткості не більше j.
Формула для заповнення таблиці матиме такий вигляд:
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i])
де f[i][j] – максимальна вартість, яку можна отримати серед перших i предметів, використовуючи рюкзак місткості не більше ніж j, w[i] і v[i] – вага і вартість i-го предмета.
Суть цієї формули полягає в тому, що для кожного предмета ми можемо розв’язати дві підзадачі: додати його до рюкзака чи не додавати. Якщо ми не додаємо предмет, то максимальна вартість дорівнюватиме максимальній вартості серед перших i-1 предметів і рюкзака місткості j. Якщо ми додаємо предмет, то максимальна вартість дорівнюватиме сумі вартості цього предмета і максимальної вартості серед перших i-1 предметів і рюкзака місткості j-вагу[i].
У результаті заповнення таблиці, відповіддю на вихідну задачу буде максимальна вартість серед перших n предметів і рюкзака місткості не більше W, де n – кількість предметів, W – місткість рюкзака.
Наприклад, для набору предметів із вагами [3, 4, 5] і вартістю [4, 5, 6] та рюкзака місткістю 8, таблиця заповнення матиме такий вигляд:
w\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 4 | 4 | 4 |
Максимальна вартість рюкзака для цього набору предметів і місткості 8 дорівнює 9.
Усі ці приклади демонструють ефективність і універсальність методу ДП у розв’язанні різних завдань;
Як і будь-який інший алгоритм, метод він має свої переваги та недоліки. Розглянемо їх детальніше.
Переваги:
Недоліки:
У майбутньому метод динамічного програмування продовжуватиме використовуватися в різних галузях, як-от фінанси, виробництво, транспорт і багатьох інших, для розв’язання складних завдань оптимізації. Однак, необхідно продовжувати дослідження в галузі розроблення нових алгоритмів, які будуть більш ефективні та універсальні для вирішення різних завдань.
Динамічне програмування - це підхід до розв'язання оптимізаційних задач. Він полягає в розбитті задачі на підзадачі, збереженні результатів цих підзадач для подальшого використання. Я часто використовую його, коли потрібно ефективно розв'язати задачу, яка може бути розбита на підзадачі.
Метод динамічного програмування може істотно прискорити розв'язання задачі, якщо вона має певну структуру: велику кількість підзадач, що перекриваються. Це дає змогу економити час виконання, уникаючи повторного обчислення одних і тих самих підзадач.
Динамічне програмування часто застосовується для розв'язання задач комбінаторики, оптимізації, пошуку в графах і динамічного планування в робототехніці.
Таблиця динамічного програмування - це засіб, який я використовую для зберігання проміжних результатів підзадач. Це допомагає уникнути повторного обчислення тих самих підзадач, що прискорює процес розв'язання задачі.
Практично будь-яка мова програмування може підтримувати динамічне програмування. Важлива не стільки конкретна технологія, скільки розуміння підходу і принципів динамічного програмування.
Мемоїзація - це техніка збереження результатів функції для запобігання повторних обчислень. Я часто використовую мемоїзацію в динамічному програмуванні, щоб зберегти результати підзадач і повторно використовувати їх, якщо вони потрібні пізніше.
🔎 У вас є запитання про метод динамічного програмування? Не соромтеся поставити їх у коментарях