Динамічне програмування — це концепція, розроблена Річардом Беллманом, математиком і економістом.
У той час Беллман шукав спосіб вирішення складних задач оптимізації. Проблеми оптимізації вимагають вибору найкращого рішення з набору варіантів.
Прикладом задачі оптимізації є задача комівояжера. Мета полягає в тому, щоб знайти найкоротший маршрут, щоб продавець міг відвідати кожне місто рівно один раз і повернутися до початкового міста.
Підхід Беллмана до цих проблем полягав у тому, щоб розбити їх на менші підпроблеми та вирішити підпроблеми від найменших до найбільших. Потім він зберігав результати підпроблем і повторно використовував їх для вирішення більших підпроблем. Це основна ідея динамічного програмування.
Що таке динамічне програмування?
Динамічне програмування вирішує проблеми оптимізації, розбиваючи їх на менші підпроблеми, розв’язуючи кожну підпроблему один раз і зберігаючи їхні рішення, щоб їх можна було повторно використовувати та комбінувати для вирішення більшої проблеми. Проблеми вирішуються від найменших до найбільших, що дозволяє повторно використовувати рішення.
Як працює динамічне програмування?
Вирішення задачі за допомогою динамічного програмування включає наступні кроки:
Щоб побачити це в дії, ми обчислюємо 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 кілограмів. У вас є список предметів, які ви можете взяти з собою, разом із їх значеннями та вагою, як показано в таблиці нижче:
ПунктВартістьВага Намет2003Спальний мішок1502Плита501Їжа1002Пляшка з водою100,5Аптечка251
Виберіть підмножину предметів, які потрібно принести, щоб загальна вартість предметів була максимальною, а загальна вага була меншою або дорівнювала місткості рюкзака, яка становить 15 кілограмів.
Реальні застосування проблеми рюкзака включають вибір цінних паперів для додавання до портфеля, щоб мінімізувати ризик і максимізувати прибуток, а також знайти найменш марнотратні способи скорочення сировини.
#2. Проблема планування
Задача планування — це задача оптимізації, метою якої є оптимальне призначення завдань набору ресурсів. Ресурсами можуть бути машини, персонал або інші ресурси, які використовуються для виконання завдань.
Нижче наведено приклад проблеми планування:
Уявіть, що ви менеджер проекту, який відповідає за планування набору завдань, які має виконати команда співробітників. Кожне завдання має час початку, час завершення та список співробітників, які кваліфіковані для його виконання.
Ось таблиця, яка описує завдання та їх характеристики:
Завдання Час початку Час закінчення Кваліфіковані співробітники T1911A, B, CT21012A, CT31113B, CT41214A, B
Призначте кожне завдання одному співробітнику, щоб мінімізувати загальний час виконання.
З проблемою планування можна зіткнутися у обробній промисловості, коли намагаються оптимізувати розподіл ресурсів, таких як машини, матеріали, інструменти та робоча сила.
З нею також можна зіткнутися в охороні здоров’я під час оптимізації використання ліжок, персоналу та медичних матеріалів. Інші галузі, де може виникнути ця проблема, це управління проектами, управління ланцюгом постачання та освіта.
#3. Проблема комівояжера
Джерело: Вікіпедія
Це одна з найбільш вивчених задач оптимізації, яку можна вирішити за допомогою динамічного програмування.
Задача комівояжера містить список міст і відстані між кожною парою міст. Вам потрібно знайти найкоротший можливий маршрут, який відвідує кожне місто рівно один раз і повертає до міста відправлення.
Приклад проблеми комівояжера наведено нижче:
Уявіть, що ви продавець, якому потрібно відвідати кілька міст за найкоротший час. У вас є список міст, які вам потрібно відвідати, і відстані між кожною парою міст, як показано в таблиці нижче:
МістоABCDEA010152030B100352515C153503020D202530010E301520100
З проблемою комівояжера можна зіткнутися в індустрії дозвілля, коли намагаються спланувати маршрути для туристів, у логістиці, коли планують доставку товарів, у транспорті, коли планують автобусні маршрути, а також у сфері продажів тощо.
Очевидно, що динамічне програмування має багато реальних застосувань, що допомагає дізнатися про нього більше.
Розгляньте наступні ресурси, щоб розкрити свої знання динамічного програмування.
Ресурси
Динамічне програмування Річарда Беллмана
Динамічне програмування — це книга Річарда Беллмана, який придумав динамічне програмування та розвинув його на ранніх стадіях.
Книга написана у легкій для розуміння формі, яка вимагає лише базових знань математики та обчислення, щоб зрозуміти текст. У книзі Беллман представляє математичну теорію багатоетапного процесу прийняття рішень, який є ключовим у динамічному програмуванні.
Потім у книзі розглядаються проблеми вузьких місць у багатостадійних виробничих процесах, теореми існування та унікальності та оптимальне рівняння запасів.
Найкраще в книзі те, що Беллман пропонує приклади багатьох складних проблем у таких галузях, як логістика, теорія планування, теорія зв’язку, математична економіка та процеси керування, і показує, як динамічне програмування може вирішити ці проблеми.
Книга доступна у версіях для Kindle, у твердій та м’якій обкладинках.
Магістерський курс Алгоритми динамічного програмування
Цей магістерський курс з алгоритмів динамічного програмування від Udemy пропонують Апаар Камал, інженер-програміст Google, і Пратік Наранг, який також працював з Google.
Курс оптимізований, щоб допомогти учням досягти успіху в змаганнях з програмування, які включають багато проблем, які вимагають динамічного програмування.
Окрім учасників програмування, курс ідеально підходить для програмістів, які хочуть покращити своє розуміння алгоритмів, і людей, які готуються до співбесід з програмування та онлайн-раундів програмування.
Курс, який триває понад 40 годин, глибоко охоплює динамічне програмування. Спочатку курс пропонує освіжити знання про такі поняття, як рекурсія та зворотне відстеження.
Потім охоплює динамічне програмування в теорії ігор, рядки, дерева та графіки, піднесення матриці до степеня, бітові маски, комбінаторику та підпослідовності, проблеми розділення та багатовимірне динамічне програмування, серед багатьох інших концепцій.
Основи конкурентного програмування, основні алгоритми
Udemy пропонує курс «Основи конкурентного програмування» від Пратіка Наранга та Амал Камаар, який охоплює динамічне програмування, математику, теорію чисел і розширені структури даних і алгоритми у спосіб, який є корисним і актуальним для конкурентоспроможних програмістів.
Курс пропонує відновити знання про структури даних і алгоритми, перш ніж занурюватися в більш складні алгоритми та методи, які стануть у нагоді в конкурентному програмуванні.
Курс охоплює динамічне програмування, математику, теорію ігор, зіставлення шаблонів, бітове маскування та безліч передових алгоритмів, які використовуються та перевіряються на змаганнях з програмування.
Курс Udemy поділений на 10 модулів і 42 розділи, і після кожного розділу міститься багато практичних запитань. Цей курс-бестселер обов’язковий для всіх, хто цікавиться змагальним програмуванням.
Заключні слова
Динамічне програмування є корисною навичкою для будь-якого програміста, щоб навчитися вдосконалювати своє вирішення проблем реального світу. Тому програмістам варто розглянути пропоновані ресурси, щоб додати цей важливий інструмент до свого інструментарію.
Далі ви можете перевірити мови програмування для використання в науці про дані.