Динамическое программирование

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

Термин был введён американским математиком Ричардом Беллманом в 1950-х годах. В этом контексте слово «программирование» используется в значении «планирование» или «составление оптимального плана действий», а не написание компьютерного кода.

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

Применимость динамического программирования к задаче определяется наличием у неё двух фундаментальных свойств.

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

Центральным концептом метода является принцип оптимальности Беллмана (англ. 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) — термин, введённый Беллманом для обозначения экспоненциального роста числа состояний и, как следствие, вычислительной сложности, при увеличении числа переменных, описывающих состояние системы. Это ограничивает практическое применение точного ДП для задач очень большой размерности.

Связанные понятия

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