Динамическое программирование и уравнение Беллмана
Что даст эта глава, кроме формулы Беллмана
Здесь вы изучаете класс оптимизации с последовательностью решений по этапам вместо единовременного выбора всех переменных. Этот подход особенно важен для задач управления процессами во времени — бюджеты по периодам, управление запасами, выбор стратегий в состояниях системы.
Главный практический результат главы — умение правильно выбрать состояние — хранить в нём только то, что нужно для будущих решений. От этого зависит, останется ли модель решаемой и полезной.
После чтения вы различаете классическое ЗЛП и ДП Беллмана по структуре задачи — единый вектор решений или рекуррентная политика по этапам.
- Здесь — метод Р. Беллмана в математическом программировании — оптимальное управление по этапам, уравнение Беллмана.
- В алгоритмах и лаборатории — мемоизация и таблицы для задач вроде рюкзака на одном горизонте. Идея "запомнить подзадачу" родственна, но постановка и термины другие.
Динамическое программирование (ДП) в исследовании операций применяют, когда процесс разбивается на этапы (периоды, шаги, станции), на каждом этапе принимается решение, а эффект накапливается. Вместо перебора всех траекторий используют принцип оптимальности Беллмана — оптимальная стратегия остаётся оптимальной на любом хвосте процесса.
Идея одной фразой
"Если вы знаете лучший способ пройти от состояния
sдо конца, то любой оптимальный путь доs+ этот хвост — оптимальный путь с самого начала".
Состояние s — всё, что нужно помнить о прошлом (остаток бюджета, текущий узел графа, объём запаса). Управление u — решение на шаге (куда поехать, сколько вложить). Переход s' = f(s, u) — что получится после шага.
Когда ДП уместно
| Признак | Пояснение |
|---|---|
| Многоэтапность | решения u₁, u₂, …, u_T |
| Состояние | sₜ описывает "где мы" после этапа t |
| Разделимость цели | сумма (или произведение в лог-масштабе) вкладов этапов |
| Маркировка | sₜ₊₁ = f(sₜ, uₜ) — переход известен |
Классика — кратчайший путь, распределение инвестиций по годам, управление запасами, разбиение ресурса на части.
Общая схема
- Определить этапы
t = 1, …, T. - Ввести состояние
sₜ(достаточная информация для будущего). - Допустимые управления
uₜ ∈ U(sₜ). - Переход
sₜ₊₁ = f(sₜ, uₜ). - Немедленный выигрыш (или затраты)
gₜ(sₜ, uₜ). - Цель — максимизировать (или минимизировать) суммарный показатель.
Уравнение Беллмана
Пусть Fₜ(s) — максимальная суммарная выгода с этапа t до конца, если в начале этапа t состояние s.
Рекуррентное соотношение (max) —
Fₜ(s) = max over u ∈ U(s) [ gₜ(s, u) + Fₜ₊₁( f(s, u) ) ]
Разбор формулы по частям —
| Часть | Смысл |
|---|---|
Fₜ(s) | лучший суммарный результат с этапа t до конца, если сейчас состояние s |
max over u | перебираем все допустимые решения на этом шаге |
gₜ(s, u) | немедленный выигрыш (или затрата) на этом шаге |
Fₜ₊₁(f(s,u)) | лучший хвост после перехода в новое состояние |
g + F | складываем "сейчас" и "потом" — аддитивная цель |
Граничное условие на последнем этапе T —
F_T(s) = g_T(s, u) или F_{T+1}(s) = 0
(Зависит от постановки — иногда на T только терминальная награда.)
Прямой проход (табуляция) — считают F_T, затем F_{T−1}, …, до F₁(s₀) — оптимальное значение.
Обратный проход (восстановление стратегии) — зная Fₜ, на каждом s запоминают лучшее u*; затем от s₀ идут вперёд по u*.
Минимизация затрат
Заменяют max на min, выигрыш g на стоимость h —
Gₜ(s) = min_u [ hₜ(s, u) + Gₜ₊₁(f(s,u)) ]
Пример — кратчайший путь на сетке
Граф с слоями (этапами) — вершины на уровне t. Состояние — вершина v на слое t. Управление — выбрать ребро к слою t+1.
Fₜ(v) = min over (v→w) [ c(v,w) + Fₜ₊₁(w) ]
База — F_T(w) = 0 (или расстояние до "стока"). Заполнение от T−1 к 0 даёт длины кратчайших путей — это ДП, не путать с однократным Дейкстрой на полном графе без слоёв.
Полный разбор — DAG из четырёх этапов
Вершины S (старт) → слой 1 — A, B → слой 2 — C, D → T (сток). Рёбра и длины —
| Ребро | c |
|---|---|
| S→A | 4 |
| S→B | 2 |
| A→C | 3 |
| A→D | 6 |
| B→C | 1 |
| B→D | 4 |
| C→T | 2 |
| D→T | 3 |
Этапы t = 2, 1, 0 (обратный проход к старту). Состояние — текущая вершина. F_T(T)=0.
t = 2 (из C или D в T) —
F₂(C) = c(C,T) + F_T(T) = 2 + 0 = 2
F₂(D) = 3 + 0 = 3
t = 1 (из A или B в C/D) —
F₁(A) = min( c(A,C)+F₂(C), c(A,D)+F₂(D) ) = min(3+2, 6+3) = 5
F₁(B) = min( 1+2, 4+3 ) = 3
t = 0 (из S) —
F₀(S) = min( 4+5, 2+3 ) = 5
Оптимальная стоимость 5 по пути S→B→C→T (2+1+2). Восстановление — на t=0 выбрали B; на t=1 из B — C; на t=2 — T.
| Этап | Таблица F | Запомнить choice |
|---|---|---|
| Обратный проход | заполняем от T к S | choice[t][v] = лучший следующий узел |
| Прямой проход | от S по choice | получаем маршрут |
Та же логика — развёртывание релизов по неделям, маршрут пакетов по стадиям конвейера, цепочка этапов CI, если стоимость этапа аддитивна и нет циклов.
Пример — распределение ресурса
Инвестору доступно S единиц ресурса на T проектов. На проект t вкладывают uₜ ≥ 0, Σuₜ ≤ S, доход gₜ(uₜ) (возрастающий, но с убывающей отдачей).
Состояние на этапе t — остаток ресурса s.
Fₜ(s) = max_{0 ≤ u ≤ s} [ gₜ(u) + Fₜ₊₁(s − u) ]
F_{T+1}(s) = 0
Перебор u по сетке 0…s — табуляция. В коде массив dp[t][s].
Мини-таблица (T = 3, S = 4, доход gₜ(u) = u для простоты)
| t \ s | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 3 | 0 | 1 | 2 | 3 | 4 |
| 2 | … | … | … | … | 4 |
| 1 | … | … | … | … | … |
| 0 | … | … | … | … | ответ |
Заполнение снизу вверх — F₃(s)=s; для t=2 и состояния s=4 перебирают u=0,1,2,3,4 и берут max(u + F₃(4−u)) — это прямое применение уравнения Беллмана. Сложность O(T·S·U), если на шаге U допустимых решений — узкое место при больших сетках.
Свойства, без которых Беллман не работает
| Свойство | Смысл |
|---|---|
| Оптимальная подструктура | оптимум хвоста не хуже любого подхвоста |
| Отсутствие "памяти" лишнего | s должно быть достаточным |
| Аддитивность (часто) | цель — сумма по этапам |
Если завтрашний оптимум зависит от всей истории помимо s, состояние выбрано узко — рекуррентная формула неверна.
Организация вычислений
На практике ДП — это таблица F[t][s] (или одномерный массив, если состояние скалярно).
| Проход | Порядок | Что получаем |
|---|---|---|
Обратный (от T к 1) | сначала F_T, затем F_{T-1}, … | оптимальное значение F_1(s₀) |
Прямой (от 1 к T) | по сохранённым u*(t,s) | оптимальная стратегия — последовательность решений |
Правила заполнения
- Зафиксировать сетку состояний — все допустимые
sна каждом этапе (для дискретного рюкзака —0…W). - На последнем этапе задать граничное условие (
F_TилиF_{T+1} ≡ 0). - Для каждого
(t, s)перебрать допустимыеu, вычислитьgₜ(s,u) + F_{t+1}(f(s,u)), записать максимум иchoice[t][s] = u*. - Восстановить ответ — от
s₀идти вперёд, подставляяu*и обновляяs.
АЛГОРИТМ ДП_табуляция()
инициализировать F[T+1][·] по граничному условию
для t от T-1 до 1
для каждого состояния s на этапе t
F[t][s] := max по u из U(s) ( g(t,s,u) + F[t+1][ f(s,u) ] )
choice[t][s] := аргумент максимума u
конец
конец
s := s0
для t от 1 до T
u := choice[t][s]
s := f(s, u)
конец
вернуть F[1][s0], траекторию u
КОНЕЦ
Сложность чаще всего O(T · |S| · |U|) — узкое место при большом |S|.
Когда ДП применимо, а когда нет
| Подходит | С осторожностью / не подходит |
|---|---|
| этапы явно выделены (периоды, шаги, слои графа) | одновременный выбор тысяч xⱼ без структуры → ЗЛП |
| аддитивная (или лог-аддитивная) цель | сильная нелинейность без разбиения |
| состояние конечное и умеренное | ` |
марковский переход s' = f(s,u) | нужна вся история → расширять состояние |
Практический тест — можно ли ответить на вопрос: "какие одни числа описывают ситуацию перед шагом t, чтобы будущее не зависело от лишних деталей прошлого?" Если да — кандидат на ДП.
Пример — целочисленный выбор с аддитивной целью
Типовой пример — максимизировать сумму вкладов fᵢ(xᵢ), где каждая переменная целочисленная (часто xᵢ ∈ {0, 1}), и выполняется одно скалярное ограничение на "вес":
max Σᵢ fᵢ(xᵢ)
при Σᵢ αᵢ xᵢ ≤ b , xᵢ ∈ {0, 1} (или целые в диапазоне)
Этапы — номера объектов i = 1, …, n. Состояние на этапе i — остаток ресурса s (сколько ещё можно "потратить"). Управление — u ∈ {0, 1} (взять объект i или нет).
Fᵢ(s) = max( Fᵢ₊₁(s), fᵢ(1) + Fᵢ₊₁(s − αᵢ) ) при s ≥ αᵢ
F_{n+1}(s) = 0. Ответ — F₁(b).
Числовой скетч. n = 3, лимит b = 5, веса (α₁,α₂,α₃) = (2, 3, 1), ценности (3, 4, 2) —
s | F₃(s) | F₂(s) | F₁(s) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 2 | 2 | 2 |
| 2 | 2 | 2 | 3 |
| 3 | 2 | 4 | 4 |
| 4 | 2 | 4 | 6 |
| 5 | 2 | 6 | 7 |
Оптимум 7 — берём объекты 1 и 2 (2+3 ≤ 5, ценность 3+4). Это тот же шаблон, что 0/1-рюкзак в алгоритмах, только в терминах Беллмана.
Если ослабить требование xᵢ ∈ 1 до 0 ≤ xᵢ ≤ 1, задача станет ЗЛП и решится симплексом. Целочисленность — причина перейти к ДП или к MIP-солверу.
Сравнение с ЗЛП и симплексом
| ЗЛП / симплекс | ДП Беллмана | |
|---|---|---|
| Структура | глобальные xⱼ | этапы, локальные uₜ |
| Размерность | n переменных | часто `T × |
| Нелинейность | только линейное | допускается нелинейное gₜ |
| Целочисленность | отдельные методы | естественно при дискретном s |
Многие задачи можно записать и как ЗЛП, и как ДП; ДП выигрывает при малых T и структурированном состоянии.
Реализация в коде (скелет)
Код ITЗагрузка примера кода…
g(t,u) — доход на этапе. Для восстановления u* хранят вторую таблицу choice[t][s].
Связь с алгоритмическим DP
| Беллман (МП) | Алгоритмы (рюкзак) |
|---|---|
этапы t, состояние s | "предметы 1..i", ёмкость W |
Fᵢ(s) = max_u … | dp[i][w] = max(взять, не брать) |
| уравнение Беллмана | та же рекуррентная идея |
Статья Нотация Большое O рекомендует включать ДП в анализ сложности — после этого раздела вы понимаете откуда взялась таблица dp[i][w].
Мост к "рюкзаку" (алгоритмический DP)
0/1-рюкзак — предметы i = 1..n, вес wᵢ, ценность vᵢ, ёмкость W. Состояние: (i, остаток_веса). Рекуррентно:
F(i, cap) = max( F(i−1, cap), vᵢ + F(i−1, cap − wᵢ) ) если wᵢ ≤ cap
Это тот же шаблон Fₜ(s) = max_u [ g + F_{t+1} ] — этап — "рассмотреть предмет i", управление — "взять / не взять", состояние — оставшийся вес. Таблица dp[i][cap] в коде — дискретная версия функции Беллмана.
| Беллман (МП) | Рюкзак (код) |
|---|---|
этап t | индекс предмета i |
состояние s | остаток ёмкости |
gₜ(s,u) | ценность, если взяли предмет |
обратный проход по t | цикл i от n до 1 |
Практика
- Решатели для больших LP; ДП — свой цикл на Python/C++.
- В ML динамическое программирование встречается в HMM, RL (уравнение Беллмана для value function) — та же философия "значение состояния + рекурсия".
Ограничения и цена размерности
Главная практическая проблема ДП - рост пространства состояний —
- если состояние многомерное (
s = (запас, позиция, время, режим)), таблица растёт экспоненциально; - время вычислений часто
O(T * |S| * |U|), и именно|S|становится критическим; - приходится делать агрегирование состояний, дискретизацию, либо переходить к приближённым методам.
Это называют "проклятием размерности". Поэтому хороший дизайн состояния так же важен, как правильная рекуррентная формула.
Чек-лист корректной постановки ДП
- Состояние действительно содержит всю нужную информацию для будущего.
- Допустимые действия зависят только от текущего состояния.
- Переход
f(s,u)детерминирован или его вероятности известны. - Цель аддитивна (или сведена к аддитивной преобразованием).
- Задано корректное граничное условие.
Дальше — инструменты в Python, итоги.