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

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Вступ

Динамічне програмування дозволяє розв’язувати поставлену задачу на основі об’єднання розв’язків знайдених для допоміжних задач.

При цьому варто зазначити, що термін програмування в даному контексті базується на основі табличного методу, а не написанні комп’ютерної програми. Крім того, якщо в методові розбиття задача ділиться на декілька незалежних між собою задач, кожна з яких вирішується рекурсивно, після чого із розв’язків проміжних задач і формується розв’язок початкової задачі, то динамічне ж програмування, навпаки, застосовується тільки тоді, коли проміжні задачі не є незалежними, тобто різні допоміжні задачі використовують розв’язки одних і тих же підзадач, причому в алгоритмі динамічного програмування кожна проміжна задача вирішується тільки один раз, після чого відповідь зберігається в таблиці. Останнє дає можливість уникати одних і тих же обрахувань кожного разу, коли працюємо з даною підзадачею.

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

Процес розробки алгоритмів динамічного програмування можна розбити на 4 нижченаведені етапи:

1. Опис структури оптимального розв’язку.

2. Рекурсивне визначення значення, що відповідає оптимальному розв’язку.

3. Обчислення значення, що відповідає оптимальному рішенню за допомогою методу висхідного аналізу.

4. Отримання оптимального розв’язку на основі інформації, отриманої на попередніх кроках.

Етапи 1-3 складають основу методу динамічного програмування. Етап 4 можна пропустити, якщо треба дізнатись тільки значення, що відповідає оптимальному. На 4 кроці інколи використовується додаткова інформація, отримана із попереднього, щоб полегшити процес побудови оптимального рішення.

Теорія рішень

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

Нехай О* - деяка операція, яка розбивається на m послідовних кроків.

Нехай W – міра ефективності цієї операції, припустимо, що вона складається з суми ефективностей на кожному кроці:

$\sum_{i=1}^{m}{ w_i }$

Позначимо X=(x₁,x₂,…x_m) – (х_i відповідає і-ому кроку) послідовність дій яка впливає на виграш(ефективність) в цілому і на виграш на кожному кроці або просто керування. Задача зводиться до пошуку такого Х^* при якому W=> max, його будемо називати оптимальним управлінням, а виграш на ньому:

W=max{W(x)}

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

Тобто управління на і-ому кроці повинне обиратися таким чином, щоб максимальною була сума виграшів на усіх кроках, що залишились включаючи поточний – Це і є зло**учий принцип оптимальності Белмана.

Приклад

Кожен крок повинен обиратися з врахуванням наслідків у майбутньому, себто програю на даному кроці – виграю на інших.

Вибираємо затрати на і-ому кроці не так, щоб вони були мінімальними, а щоб сума затрат для всіх що лишилась була мінімальною.

Плануємо останній m-ий крок, тому процес динамічного програмування розвертають з кінця.

Ми шукаємо умовне оптимальне керування і умовні оптимальні затрати, коли йдемо з кінця до початку, а потім оптимальне керування і затрати – від початку до кінця, фактично перевертаємо потрібні рекомендація з кінця на початок, і знайдемо безумовне оптимальне керування x*, що складається з оптимального крокового керування x*1, x*2, …, x*m.

Кроки – 3+4=7.

Отже, оптимальних керувань x* отримали 3 (позначимо рух вліво – л, вверх - в):

• x*₁ = (л, в, в, л, л, в, л);
• x*₂ = (л, в, л, в, л, в, л);
• x*₃ = (л, в, л, л, в, в, л),

А оптимальні затрати = 26.

• W*₁ = (1, 1, 1, 9, 6, 2, 6);
• W*₂ = (1, 1, 9, 1, 6, 2, 6);
• W*₃ = (1, 1, 9, 6, 1, 2, 6).