Динамично програмиране

Динамично програмиране (ДП; англ. dynamic programming, DP) — това е метод за решаване на сложни задачи за оптимизация, основан на разбиването на изходната задача на последователност от по-прости подзадачи. Методът се прилага към многостъпкови процеси на вземане на решения, при които оптималното решение на цялата задача може да бъде построено от оптималните решения на нейните подзадачи.

Терминът е въведен от американския математик Ричард Белман през 50-те години на XX век. В този контекст думата „програмиране" се използва в смисъл на „планиране" или „съставяне на оптимален план за действие", а не писане на компютърен код.

Ключови свойства и теореми

Приложимостта на динамичното програмиране към дадена задача се определя от наличието на две фундаментални свойства.

Принцип на оптималността на Белман

Централната концепция на метода е принципът на оптималността на Белман (англ. Bellman's principle of optimality). Той гласи: каквито и да са първоначалното състояние и първоначалното решение, последващите решения трябва да съставляват оптимална стратегия спрямо състоянието, получено в резултат на първото решение.

С други думи, всяка част от оптималната траектория сама по себе си е оптимална. Това свойство позволява да се раздели общата задача на последователност от по-прости подзадачи и да се решават рекурсивно.

Припокриващи се подзадачи

Задачата притежава свойството припокриващи се подзадачи (англ. overlapping subproblems), ако при рекурсивното ѝ решаване едни и същи подзадачи възникват многократно. ДП позволява да се избегнат повторни изчисления, като се запазват решенията на вече срещнатите подзадачи (този похват се нарича мемоизация или табулация), което значително повишава ефективността в сравнение с наивното рекурсивно изброяване.

Уравнение на Белман

От принципа на оптималността произтича основното рекурентно съотношение на метода — уравнението на Белман. То свързва „стойността" (оптималната печалба или цена) на текущото състояние със стойностите на следващите състояния. В общ вид за детерминиран многостъпков процес с адитивна целева функция то има вида:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

където:

• $k$ — номер на стъпката (от $m$ до 1);
• $x$ — състояние на системата на стъпка $k-1$;
• $y$ — управляемото решение, взимано на стъпка $k$;
• ${\phi }_k(x,y)$ — печалба (или цена) на k-тата стъпка;
• $f_k(x,y)$ — функция, задаваща новото състояние на системата;
• $V_k(s)$ — оптималната стойност на целевата функция за подзадачата, започваща на стъпка $k$ в състояние $s$.

Уравнението се решава последователно, като правило „от края", движейки се от последната стъпка към първата.

Примери за приложение

• Задача за най-краткия път в граф: Тази задача притежава свойството на оптимална подструктура, тъй като всеки участък от най-краткия път сам е най-кратък. Алгоритмите на Белман-Форд и Флойд-Уоршал са класически примери за приложение на ДП за решаването на тази задача.
• Задача за раницата: Задача за оптималното запълване на раница с ограничен капацитет с предмети с различна стойност и тегло. ДП позволява да се реши тази задача, като предметите се разглеждат последователно и на всяка стъпка се изчислява максималната стойност за всички възможни стойности на оставащия капацитет.
• Задача за разпределение на ресурси: Разпределение на ограничен ресурс (например инвестиции) между няколко проекта с цел максимизиране на общия ефект.

Ограничения

Главното ограничение на метода е проклятието на размерността (англ. curse of dimensionality) — термин, въведен от Белман за обозначаване на експоненциалния растеж на броя на състоянията и, като следствие, на изчислителната сложност при увеличаване на броя на променливите, описващи състоянието на системата. Това ограничава практическото приложение на точното ДП за задачи с много голяма размерност.

Свързани понятия

• Изследване на операциите
• Теория на оптималното управление
• Марковски процес на вземане на решения (стохастично обобщение)
• Уравнение на Хамилтон — Якоби — Белман (аналог за непрекъснато време)