Динамічне програмування, основні принципи
Для вибору оптимального рішення при виконанні завдань програмування іноді потрібно перебирати велику кількість комбінацій даних, що навантажує пам`ять персонального комп`ютера. До таких методів відноситься, наприклад, метод програмування «розділяй і володарюй». В даному випадку алгоритмом передбачено поділ завдання на окремі дрібні підзадачі. Такий метод застосовується тільки в тих випадках, коли дрібні підзадачі незалежні між собою. Для того щоб уникнути виконання зайвої роботи в тому випадку, якщо підзадачі взаємозалежні, використовується метод динамічного програмування, запропонований американцем Р.Беллманом в 50-х роках.
Відео: Основні принципи об`єктно-орієнтованого програмування. Що таке ООП і навіщо воно потрібне?
суть методу
Відео: 2. Алгоритми і структури даних. Жадібні алгоритми | Технострим
Динамічне програмування полягає у визначенні оптимального рішення n-мірної задачі, розділяючи її n окремих етапів. Кожен з них є підзадачею по відношенню до однієї змінної.
Основною перевагою такого підходу можна вважати те, що розробники займаються одновимірними оптимізаційними задачами підзадач замість n-мірної задачі, а вирішення головного завдання збирається «знизу вгору».
Доцільно застосовувати динамічне програмування в тих випадках, коли підзадачі взаємопов`язані, тобто мають загальні модулі. Алгоритмом передбачено вирішення кожної з підзадач один раз, і збереження відповідей виконується в спеціальній таблиці. Це дає можливість не обчислювати відповідь заново при зустрічі з аналогічною підзадачею.
Завдання динамічного програмування вирішує питання оптимізації. Автором цього методу Р. Беллманом був сформульований принцип оптимальності: яким би не було початковий стан на кожному з кроків і рішення, визначене на цьому кроці, все такі вибираються оптимальними по відношенню до того стану, який приймає система в кінці кроку.
Метод удосконалить виконання завдань, що вирішуються за допомогою перебору варіантів або рекурсій.
Побудова алгоритму завдання
Динамічне програмування передбачає побудову такого алгоритму завдань, при якому завдання так розбивається на дві або більше підзадач, щоб її рішення складалося з оптимального вирішення всіх підзадач, що входять в неї. Далі виникає необхідність в написанні рекуррентного співвідношення і обчисленні оптимального значення параметра для завдання в цілому.
Іноді на 3-му кроці потрібно додатково запам`ятовувати деяку допоміжну інформацію про хід виконання кожної підзадачі. Це називається зворотним ходом.
застосування методу
Динамічне програмування застосовується при наявності двох характерних ознак:
- оптимальність для підзадач;
- наявність в завданні перекриваються підзадач.
Вирішуючи оптимізаційних задач методом динамічного програмування, спочатку необхідно описати структуру рішення. Завдання має оптимальністю, якщо рішення задачі складається з оптимальних рішень її підзадач. У цьому випадку доцільно використовувати динамічне програмування.
Друге властивість завдання, істотне при цьому методі, - невелике число підзадач. Рекурсивне рішення задачі використовує одні й ті ж перекриваються підзадачі, кількість яких залежить від розміру вихідної інформації. Відповідь зберігається в спеціальній таблиці, програма економить час, користуючись цими даними.
Особливо ефективним є застосування динамічного програмування тоді, коли по суті завдання потрібно приймати рішення поетапно. Наприклад, розглянемо простий приклад завдання заміни і ремонту устаткування. Припустимо, на ливарної машині заводу по виготовленню шин роблять одночасно шини в двох різних формах. У тому випадку, якщо одна з форм виходить з ладу, доводиться машину розбирати. Зрозуміло, що іноді вигідніше замінити і другу форму для того, щоб не розбирати машину на випадок, якщо і ця форма виявиться непрацездатною на наступному етапі. Тим більше, буває простіше замінити обидві працюють форми до того, як вони почнуть виходити з ладу. Метод динамічного програмування визначає найкращу стратегію в питанні про заміну таких форм, враховуючи всі чинники: вигоду від продовження експлуатації форм, втрати від простою машини, вартість забракованих шин і інше.
