Динамічне програмування є концепцією, розробленою видатним математиком і економістом Річардом Беллманом.
У свій час Беллман активно шукав методи для розв’язання складних завдань оптимізації. Задачі оптимізації передбачають знаходження найкращого варіанту з багатьох можливих рішень.
Прикладом такої задачі є задача комівояжера. Її суть полягає у визначенні найкоротшого шляху, який дозволить продавцю відвідати кожне місто лише один раз і повернутися у початкову точку.
Підхід Беллмана до розв’язання таких задач полягав у декомпозиції великої проблеми на менші підпроблеми, які розв’язуються послідовно, від найменших до найбільших. Результати розв’язання цих підпроблем зберігаються для повторного використання при розв’язанні більших, що є ключовою ідеєю динамічного програмування.
Що являє собою динамічне програмування?
Динамічне програмування використовується для вирішення оптимізаційних задач шляхом розбиття їх на дрібніші підзадачі. Кожна підзадача розв’язується лише один раз, а її рішення зберігається для повторного використання та поєднання з іншими рішеннями для розв’язання вихідної, більшої проблеми. Процес розв’язання відбувається поступово, від найменших підзадач до більших, що дозволяє ефективно використовувати вже знайдені рішення.
Як функціонує динамічне програмування?
Розв’язання задачі за допомогою динамічного програмування складається з кількох етапів:
- Визначення підзадач: велика проблема поділяється на менші, простіші підпроблеми.
- Розв’язання підзадач: кожна ідентифікована підзадача розв’язується, використовуючи рекурсію або ітерацію.
- Збереження рішень: розв’язки підзадач зберігаються для їхнього подальшого використання.
- Формування розв’язку вихідної задачі: рішення великої проблеми будується на основі вже обчислених розв’язків підзадач.
Для наочності, розглянемо обчислення 6-го числа Фібоначчі, F(6), згідно з цим алгоритмом.
Спершу, визначимо підпроблеми, які необхідно розв’язати.
F(n) = F(n-1) + F(n-2) для n > 1
Отже: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Другим етапом є розв’язання кожної підпроблеми за допомогою рекурсивної функції або ітераційного процесу. Розв’язання підпроблем відбувається від найменших до найбільших, використовуючи результати менших підпроблем повторно. Таким чином, отримуємо:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Розв’язуючи кожну з підпроблем, ми зберігаємо результати в масиві або таблиці, щоб мати можливість повторно їх використовувати при розв’язанні більших підпроблем, наприклад:
Після розв’язання всіх підпроблем, ми використовуємо ці рішення для формування розв’язку вихідної задачі.
У цьому прикладі, розв’язком вихідної задачі є 6-те число Фібоначчі, яке визначається сумою результатів F(5) і F(4), підзадач, отриманих із найбільшої задачі. Отже, результат дорівнює 8.
Де і чому використовується динамічне програмування?
Динамічне програмування знаходить застосування у тих сферах, де проблеми можна поділити на менші підзадачі, а їх рішення використовуються для вирішення більших проблем.
До цих сфер належать інформатика, економіка, математика та інженерія. В інформатиці цей метод застосовують для розв’язування задач із послідовностями, графами та цілими значеннями, а також у змагальному програмуванні.
В економіці динамічне програмування допомагає вирішувати задачі оптимізації у фінансах, виробництві та розподілі ресурсів. У математиці цей метод використовується в теорії ігор, статистиці та теорії ймовірностей для вирішення оптимізаційних задач.
В інженерії, динамічне програмування застосовується для розв’язання проблем розподілу ресурсів, планування, виробництва, зв’язку та системах керування.
Застосування динамічного програмування для розв’язання задач оптимізації має ряд переваг:
- Ефективність: Динамічне програмування може бути більш ефективним, ніж інші алгоритми оптимізації, оскільки воно усуває необхідність повторного обчислення тих самих підпроблем.
- Розв’язання великих проблем: Динамічне програмування особливо ефективне для великих оптимізаційних задач, які складно розв’язати іншими методами. Розбиття задачі на менші підпроблеми значно зменшує їх складність.
- Оптимальні рішення: Алгоритми динамічного програмування можуть знайти оптимальний розв’язок задачі, за умови правильного визначення підпроблем та цілей.
- Простота: Алгоритми динамічного програмування відносно прості для розуміння та реалізації, особливо коли проблему можна чітко визначити у певній послідовності.
- Масштабованість: Алгоритми динамічного програмування легко адаптуються до розв’язання складніших задач, шляхом додавання нових підпроблем та зміни цілей.
Отже, динамічне програмування є потужним інструментом для ефективного розв’язання задач оптимізації.
Підходи, що використовуються в динамічному програмуванні
У динамічному програмуванні застосовують два основні підходи для розв’язання оптимізаційних задач: підхід “зверху вниз” і підхід “знизу вгору”.
Підхід зверху вниз
Цей підхід також відомий як запам’ятовування. Запам’ятовування є технікою оптимізації, що прискорює виконання програм шляхом збереження результатів викликів функцій у кеші. Коли той самий результат потрібен знову, він повертається з кешу, замість повторного обчислення.
Підхід зверху вниз включає рекурсію та кешування. Рекурсія – це функція, яка викликає сама себе з простішими варіантами проблеми як аргументом. Рекурсія використовується для розбиття задачі на менші підпроблеми та їх розв’язання.
Після розв’язання підпроблеми її результат кешується для повторного використання у випадку виникнення аналогічної підпроблеми. Підхід зверху вниз є відносно простим для розуміння та реалізації, оскільки кожна підпроблема розв’язується лише один раз. Однак, недоліком цього методу є велике споживання пам’яті через рекурсію, що може призвести до помилки переповнення стека.
Підхід “знизу вгору”
Підхід “знизу вгору”, або табуляція, виключає рекурсію, замінюючи її ітерацією, що запобігає помилкам переповнення стека.
Згідно з цим підходом, велика задача розбивається на дрібніші підзадачі, а їх рішення використовуються для розв’язання більшої задачі.
Розв’язання підзадач починається з найменших і відбувається в порядку зростання, а їх результати зберігаються у матриці, масиві або таблиці – звідси і назва “табуляція”.
Збережені результати використовуються для розв’язання більших задач, які залежать від цих підзадач. Розв’язок вихідної задачі визначається шляхом розв’язання найбільшої підзадачі з використанням попередньо обчислених значень.
Перевагою цього підходу є ефективне використання пам’яті та часу, завдяки відсутності рекурсії.
Приклади задач, які можна розв’язати за допомогою динамічного програмування
Нижче наведено декілька прикладів задач, які можна ефективно розв’язувати, застосовуючи динамічне програмування.
#1. Задача про рюкзак
Рюкзак – це сумка, зазвичай з тканини або шкіри, що носиться на спині, яку використовують для перенесення речей, наприклад, солдати чи туристи.
У задачі про рюкзак, маючи обмежену місткість рюкзака, потрібно обрати набір предметів, кожен з яких має свою вартість та вагу. Метою є вибір такого набору предметів, щоб їхня сумарна вартість була максимальною, а загальна вага не перевищувала місткість рюкзака.
Розглянемо приклад:
Уявіть, що ви збираєтеся в похід і маєте рюкзак місткістю 15 кілограмів. У вас є список предметів, які ви можете взяти з собою, з їхньою вартістю та вагою, як показано у таблиці нижче:
| Пункт | Вартість | Вага |
| Намет | 200 | 3 |
| Спальний мішок | 150 | 2 |
| Плита | 50 | 1 |
| Їжа | 100 | 2 |
| Пляшка з водою | 100 | 0.5 |
| Аптечка | 25 | 1 |
Виберіть набір предметів, щоб їх сумарна вартість була максимальною, а загальна вага не перевищувала 15 кілограмів.
Реальні застосування задачі про рюкзак включають вибір цінних паперів для інвестиційного портфеля для мінімізації ризику та максимізації прибутку, а також пошук найменш витратних способів скорочення використання сировини.
#2. Задача планування
Задача планування є оптимізаційною задачею, метою якої є оптимальний розподіл завдань між доступними ресурсами. Ресурсами можуть бути обладнання, персонал або інші ресурси, необхідні для виконання завдань.
Приклад задачі планування:
Уявіть себе менеджером проєкту, відповідальним за планування набору завдань, які повинна виконати команда співробітників. Кожне завдання має час початку, час завершення та список кваліфікованих співробітників.
Ось таблиця, що описує завдання та їх характеристики:
| Завдання | Час початку | Час закінчення | Кваліфіковані співробітники |
| T1 | 9 | 11 | A, B, C |
| T2 | 10 | 12 | A, C |
| T3 | 11 | 13 | B, C |
| T4 | 12 | 14 | A, B |
Розподіліть кожне завдання між одним співробітником, щоб мінімізувати загальний час виконання.
Задачі планування часто виникають у виробничій промисловості при оптимізації розподілу ресурсів, таких як обладнання, матеріали, інструменти та персонал. Також вони актуальні в охороні здоров’я для оптимізації використання ліжок, персоналу та медичних матеріалів, а також у сферах управління проєктами, постачання та освіти.
#3. Задача комівояжера
Це одна з найвідоміших задач оптимізації, яку можна ефективно розв’язувати за допомогою динамічного програмування.
Задача комівояжера включає набір міст та відстані між кожною парою міст. Потрібно знайти найкоротший маршрут, який відвідує кожне місто рівно один раз та повертається у вихідне місто.
Наприклад:
Уявіть себе продавцем, якому потрібно відвідати кілька міст за найкоротший час. У вас є список міст та відстані між ними, які наведені у таблиці:
| Місто | A | B | C | D | E |
| A | 0 | 10 | 15 | 20 | 30 |
| B | 10 | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| D | 20 | 25 | 30 | 0 | 10 |
| E | 30 | 15 | 20 | 10 | 0 |
Задача комівояжера зустрічається у багатьох сферах, наприклад, планування туристичних маршрутів, логістика доставки товарів, планування автобусних маршрутів, тощо.
Як бачимо, динамічне програмування має широке застосування в реальному житті, тому вивчення цього методу є важливим.
Розглянемо наведені нижче ресурси, які допоможуть поглибити ваші знання у цій галузі.
Ресурси
“Динамічне програмування” Річарда Беллмана
Це книга, написана автором концепції динамічного програмування, Річардом Беллманом, де він детально розглядає її основи та розвиток.
Книга викладена у доступній формі, вимагаючи лише базових знань математики. Беллман подає математичну теорію багатокрокового процесу прийняття рішень, який є ключовим у динамічному програмуванні.
У книзі також розглядаються проблеми вузьких місць у виробничих процесах, теореми існування та унікальності, а також оптимальні рівняння запасів.
Особливістю книги є наведення прикладів складних задач з різних сфер, таких як логістика, теорія планування, теорія зв’язку, математична економіка та процеси керування, з демонстрацією застосування динамічного програмування для їх вирішення.
Книга доступна у різних форматах: Kindle, твердій та м’якій обкладинках.
Магістерський курс “Алгоритми динамічного програмування”
Цей курс від Udemy пропонують інженер-програміст Google, Апаар Камал, та Пратік Наранг, який також працював у Google.
Курс розроблено для підготовки студентів до успішної участі у змаганнях з програмування, де часто виникають задачі, що потребують застосування динамічного програмування.
Окрім учасників програмування, курс підійде для програмістів, які хочуть покращити свої знання алгоритмів, та для тих, хто готується до співбесід з програмування.
Курс триває понад 40 годин та глибоко висвітлює динамічне програмування. Спочатку курс повторює такі поняття, як рекурсія та зворотне відстеження, а потім охоплює динамічне програмування в теорії ігор, рядках, деревах та графах, піднесення матриць до степеня, бітові маски, комбінаторику та підпослідовності, проблеми розбиття та багатовимірне динамічне програмування.
Курс “Основи конкурентного програмування, базові алгоритми”
Udemy пропонує курс “Основи конкурентного програмування” від Пратіка Наранга та Амал Камаара, що охоплює динамічне програмування, математику, теорію чисел та структури даних, корисні для учасників змагань з програмування.
Курс починається з повторення структур даних і алгоритмів, а потім переходить до більш складних алгоритмів та методів, необхідних у конкурентному програмуванні.
Курс охоплює динамічне програмування, математику, теорію ігор, зіставлення шаблонів, бітове маскування та інші алгоритми, які часто застосовуються на змаганнях з програмування.
Курс поділений на 10 модулів і 42 розділи, з практичними завданнями після кожного розділу. Цей курс є обов’язковим для всіх, хто цікавиться змагальним програмуванням.
Висновок
Динамічне програмування є корисним навиком для програмістів, оскільки дозволяє ефективно розв’язувати складні реальні проблеми. Тому програмістам варто вивчити цей важливий інструмент, використовуючи запропоновані ресурси.
Далі ви можете ознайомитися з мовами програмування, що застосовуються у Data Science.