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

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

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

Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах (оптимального планування), так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)

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

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

Історія

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

Слово динамічне було обране Беллманом, тому що звучало більш переконливо і краще підходило для передачі того факту, що проблема оптимального управління, яку він розв'язував цим методом, має аспект залежності від часу. Слово програмування в цьому словосполученні в дійсності до «традиційного» програмування (написання тексту програм) майже ніякого відношення не має. Це використання таке саме як і в словосполученнях лінійне програмування та математичне програмування, які фактично є синонімами для математичної оптимізації. Тут воно означає оптимальну послідовність дій, оптимальну програму для отримання розв'язку задачі. Наприклад, певний розклад подій на виставці чи в театрі теж називають програмою. Програма в даному випадку розуміється як запланована послідовність подій. Хоча, динамічне програмування, як алгоритм, часто використовується при програмуванні для розв'язку відповідних задач (див. нижче).

Огляд

Рис 1. Пошук найкоротшого шляху в графі, використовуючи оптимальну підструктуру; кругами позначено вершини графу; прямі лінії позначають одиночні ребра; хвилясті лінії позначають найкоротший шлях між двома вершинами (інші вершини на цих шляхах не показано); жирна лінія — найкоротший шлях з початкової в кінцеву точку.

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

Якщо підзадачі можуть бути вкладеними рекурсивно всередині більших задач, так що методи динамічного програмування можуть бути застосовні, то існує залежність між розв'язком загальної задачі, і розв'язком підзадач . В (методах оптимізації) це відношення виражається рівнянням Беллмана.

Динамічне програмування в методах оптимізації

З точки зору математичної оптимізації, динамічне програмування полягає в спрощенні знаходження загального оптимального розв'язку, шляхом пошуку розв'язків в підзадачах, отриманих розбиттям задачі на послідовні проміжки часу. Це виражається у визначенні послідовності значень функцій V₁, V₂, …, V_n, з аргументом y, котрий позначає стан системи в моменти часу i від 1 до n. Визначенням V_n(y) є значення, отримане в стані y в кінцевий момент часу n. Значення V_i в попередні моменти часу i = n −1, n − 2, …, 2, 1 можуть бути знайдені рухаючись назад, використовуючи рекурсивну залежність, названу рівняння Беллмана. Для i = 2, …, n, значення V_i−1 для будь-якого стану y визначається з V_i через максимізацію значення простої функції (зазвичай, суми) виграшу від рішення в момент часу i − 1 і функції V_i у новому стані системи, якби це рішення було втілено. Оскільки V_i вже було розраховано для потрібних станів, то вище наведена операція забезпечує необхідне оптимальне значення V_i−1 для цих станів. Нарешті, V₁ як початковий стан системи є значенням оптимального рішення. Оптимальне значення змінних рішення може бути відновлене одне за одним виконанням обернених у часі обчислень.

Примітки

1. (PDF). Архів оригіналу (PDF) за 10 січня 2005. Процитовано 25 січня 2012.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
2. Eddy, S. R., What is dynamic programming?, Nature Biotechnology, 22, 909—910 (2004).
3. Nocedal, J.; Wright, S. J.: Numerical Optimization, page 9, Springer, 2006.
4. Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw-Hill, . pp. 327-8.

Посилання

• І. Клейнер. Відео-лекції з динамічного програмування^{[недоступне посилання]} (рос.)