Динамічне програмування, основні принципи

Для вибору оптимального рішення при виконанні завдань програмування іноді потрібно перебирати велику кількість комбінацій даних, що навантажує пам`ять персонального комп`ютера. До таких методів відноситься, наприклад, метод програмування «розділяй і володарюй». В даному випадку алгоритмом передбачено поділ завдання на окремі дрібні підзадачі. Такий метод застосовується тільки в тих випадках, коли дрібні підзадачі незалежні між собою. Для того щоб уникнути виконання зайвої роботи в тому випадку, якщо підзадачі взаємозалежні, використовується метод динамічного програмування, запропонований американцем Р.Беллманом в 50-х роках.

Суть методу

Динамічне програмування полягає у визначенні оптимального рішення n-мірної завдання, розділяючи її n окремих етапів. Кожен з них є підзадачею по відношенню до однієї змінної.

Основною перевагою такого підходу можна вважати те, що розробники займаються одновимірними оптимізаційними задачами підзадач замість n-мірної задачі, а вирішення головного завдання збирається «знизу вгору».

Доцільно застосовувати динамічне програмування в тих випадках, коли підзадачі взаємозалежні, тобто мають спільні модулі. Алгоритмом передбачено вирішення кожної з підзадач один раз, і збереження відповідей виконується в спеціальній таблиці. Це дає можливість не обчислювати відповідь заново при зустрічі з аналогічною підзадачею.

Завдання динамічного програмування вирішує питання оптимізації. Автором цього методу Р. Беллманом був сформульований принцип оптимальності: яким би не було початковий стан на кожному з кроків і рішення, визначене на цьому кроці, все наступні вибираються оптимальними по відношенню до того стану, який приймає система в кінці кроку.

Метод удосконалить виконання завдань, що вирішуються за допомогою перебору варіантів або рекурсій.

Побудова алгоритму задачі

Динамічне програмування передбачає побудову такого алгоритму завдань, при якому задача так розбивається на дві або більше підзадач, щоб її рішення складалося з оптимального вирішення всіх підзадач, що входять до неї. Далі виникає необхідність у написанні рекуррентного співвідношення і обчисленні оптимального значення параметра для завдання в цілому.

Іноді на 3-му кроці потрібно додатково запам`ятовувати деяку допоміжну інформацію про хід виконання кожної підзадачі. Це називається зворотним ходом.

Застосування методу

Динамічне програмування застосовується при наявності двох характерних ознак:

• оптимальність для подзадач;
• наявність в задачі перекриваються підзадач.

Вирішуючи оптимізаційну задачу методом динамічного програмування, спочатку необхідно описати структуру рішення. Завдання володіє оптимальністю, якщо рішення задачі складається з оптимальних рішень її підзадач. У цьому випадку доцільно використовувати динамічне програмування.

Друга властивість завдання, істотне при цьому методі, - невелике число підзадач. Рекурсивне рішення задачі використовує одні й ті ж перекриваються підзадачі, кількість яких залежить від розміру вихідної інформації. Відповідь зберігається в спеціальній таблиці, програма економить час, користуючись цими даними.

Особливо ефективне застосування динамічного програмування тоді, коли по суті завдання потрібно приймати рішення поетапно. Наприклад, розглянемо простий приклад завдання заміни та ремонту обладнання. Припустимо, на ливарній машині заводу з виготовлення шин роблять одночасно шини в двох різних формах. У тому випадку, якщо одна з форм виходить з ладу, доводиться машину розбирати. Зрозуміло, що іноді вигідніше замінити і другу форму для того, щоб не розбирати машину на випадок, якщо і ця форма виявиться непрацездатною на наступному етапі. Тим більше, буває простіше замінити обидві працюють форми до того, як вони почнуть виходити з ладу. Метод динамічного програмування визначає найкращу стратегію в питанні про заміну таких форм, враховуючи всі фактори: вигоду від продовження експлуатації форм, втрати від простою машини, вартість забракованих шин та інше.