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

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

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

Суть методу

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


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

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

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

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

Побудова алгоритму завдання

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

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


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

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

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

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

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

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