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