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

ОБЯЗАТЕЛЬНО

Архитектору Инженеру

Два разных «динамических программирования»

• Здесь — метод Р. Беллмана в математическом программировании: оптимальное управление по этапам, уравнение Беллмана.
• В алгоритмах и лаборатории — мемоизация и таблицы для задач вроде рюкзака на одном горизонте. Идея «запомнить подзадачу» родственна, но постановка и термины другие.

Динамическое программирование (ДП) в исследовании операций применяют, когда процесс разбивается на этапы (периоды, шаги, станции), на каждом этапе принимается решение, а эффект накапливается. Вместо перебора всех траекторий используют принцип оптимальности Беллмана: оптимальная стратегия остаётся оптимальной на любом хвосте процесса.

Идея одной фразой

«Если вы знаете лучший способ пройти от состояния s до конца, то любой оптимальный путь до s + этот хвост — оптимальный путь с самого начала».

Состояние s — всё, что нужно помнить о прошлом (остаток бюджета, текущий узел графа, объём запаса). Управление u — решение на шаге (куда поехать, сколько вложить). Переход s' = f(s, u) — что получится после шага.

Когда ДП уместно

Признак	Пояснение
Многоэтапность	решения u₁, u₂, …, u_T
Состояние	sₜ описывает «где мы» после этапа t
Разделимость цели	сумма (или произведение в лог-масштабе) вкладов этапов
Маркировка	sₜ₊₁ = f(sₜ, uₜ) — переход известен

Классика: кратчайший путь, распределение инвестиций по годам, управление запасами, разбиение ресурса на части.

Общая схема

1. Определить этапы t = 1, …, T.
2. Ввести состояние sₜ (достаточная информация для будущего).
3. Допустимые управления uₜ ∈ U(sₜ).
4. Переход sₜ₊₁ = f(sₜ, uₜ).
5. Немедленный выигрыш (или затраты) gₜ(sₜ, uₜ).
6. Цель: максимизировать (или минимизировать) суммарный показатель.

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

Пусть 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, состояние выбрано узко — рекуррентная формула неверна.

Сравнение с ЗЛП и симплексом

	ЗЛП / симплекс	ДП Беллмана
Структура	глобальные xⱼ	этапы, локальные uₜ
Размерность	n переменных	часто `T ×
Нелинейность	только линейное	допускается нелинейное gₜ
Целочисленность	отдельные методы	естественно при дискретном s

Многие задачи можно записать и как ЗЛП, и как ДП; ДП выигрывает при малых T и структурированном состоянии.

Реализация в коде (скелет)

# max, дискретные состояния 0..S
T = 4
S = 10
dp = [[0] * (S + 1) for _ in range(T + 2)]

for t in range(T, 0, -1):
    for s in range(S + 1):
        best = float("-inf")
        for u in range(s + 1):
            val = g(t, u) + dp[t + 1][s - u]
            if val > best:
                best = val
        dp[t][s] = best

answer = dp[1][S]

g(t,u) — доход на этапе. Для восстановления u* хранят вторую таблицу choice[t][s].

Связь с алгоритмическим DP

Беллман (МП)	Алгоритмы (рюкзак)
этапы t, состояние s	«предметы 1..i», ёмкость W
Fᵢ(s) = max_u …	dp[i][w] = max(взять, не брать)
уравнение Беллмана	та же рекуррентная идея

Статья 311 рекомендует включать ДП в анализ сложности — после этого раздела вы понимаете откуда взялась таблица 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) — та же философия «значение состояния + рекурсия».

Дальше: инструменты в Python, итоги.

---