Динамическое программирование и уравнение Беллмана
Класс оптимизации — это категория задач, объединённых общими математическими свойствами и требованиями к методу решения, такими как линейность или нелинейность целевой функции, характер ограничений, дискретность или непрерывность переменных, а также наличие временной или пространственной структуры; принадлежность задачи к тому или иному классу, например, к задачам линейного программирования, целочисленного программирования или динамического программирования, определяет выбор наиболее эффективного алгоритма и предопределяет теоретические гарантии сходимости, причём динамическое программирование выделяется как особый класс, ориентированный на многоэтапные процессы с аддитивными критериями.
Динамическое программирование — это мощный методологический подход к решению многоэтапных оптимизационных задач, разработанный Ричардом Беллманом, который основан на декомпозиции сложной проблемы на последовательность более простых взаимосвязанных подзадач, решаемых рекурсивно, причём каждая подзадача соответствует определённому этапу процесса и определённому состоянию системы; в отличие от методов, перебирающих все варианты одновременно, динамическое программирование использует принцип оптимальности для отбрасывания заведомо неоптимальных продолжений, что позволяет радикально сократить вычислительную сложность для задач, обладающих структурой вложенных решений и аддитивной сепарабельностью целевой функции.
Беллман — это выдающийся американский математик, который в 1950-х годах разработал теорию динамического программирования и сформулировал её фундаментальный принцип оптимальности, причём его имя прочно связано с уравнением Беллмана, являющимся ядром этого подхода; он внёс огромный вклад также в теорию управления, теорию игр и исследование операций, и его работы показали, что многие сложные задачи, включая управление запасами, распределение ресурсов и планирование производственных мощностей, могут быть эффективно решены с помощью рекуррентных процедур, рассматривающих процесс от конца к началу.
Уравнение Беллмана — это фундаментальное функциональное уравнение, которое выражает оптимальное значение целевой функции для данного состояния и данного этапа через немедленный эффект от принятого решения на текущем шаге и оптимальную стоимость всех последующих шагов, причём это уравнение записывается в рекуррентной форме и связывает соседние этапы процесса; оно служит основным рабочим инструментом динамического программирования, поскольку его решение даёт не только оптимальную итоговую стоимость, но и оптимальную политику управления для каждого состояния и каждого этапа, и в дискретных задачах оно превращается в вычислимую рекуррентную формулу, а в непрерывных — в дифференциальное или интегро-дифференциальное уравнение.
Здесь вы изучаете класс оптимизации с последовательностью решений по этапам вместо единовременного выбора всех переменных. Этот подход особенно важен для задач управления процессами во времени — бюджеты по периодам, управление запасами, выбор стратегий в состояниях системы.
Главный практический результат главы — умение правильно выбрать состояние — хранить в нём только то, что нужно для будущих решений. От этого зависит, останется ли модель решаемой и полезной.
После чтения вы различаете классическое ЗЛП и ДП Беллмана по структуре задачи — единый вектор решений или рекуррентная политика по этапам.
Вектор решений — это упорядоченный набор управляющих переменных, принимаемых последовательно на каждом этапе многоэтапного процесса, который в совокупности определяет полную траекторию развития системы от начального до конечного состояния; в динамическом программировании вектор решений не находится сразу целиком, а строится поэтапно, причём на каждом этапе выбор текущего управления зависит от достигнутого состояния и от будущих последствий, и именно рекуррентное построение этого вектора с обратной или прямой прогонкой позволяет избежать перебора всех возможных комбинаций.
Рекуррентная политика по этапам — это правило или функция, которая для каждого этапа и каждого возможного состояния системы предписывает, какое управление следует применить, чтобы обеспечить оптимальное продолжение процесса от данного состояния до конца горизонта планирования; такая политика вырабатывается в процессе решения уравнения Беллмана и является стационарной или нестационарной в зависимости от того, зависит ли она от номера этапа, и её главная ценность в том, что она задаёт не одно единственное решение для фиксированных начальных условий, а целое семейство оптимальных стратегий, готовых к применению при любых возможных состояниях.
Этап — это дискретный временной или логический интервал в рамках многоэтапной оптимизационной задачи, на котором принимается одно или несколько решений, изменяющих состояние системы, причём число этапов может быть конечным или бесконечным, но в классическом динамическом программировании оно конечно и задано заранее; каждый этап характеризуется множеством допустимых состояний, множеством доступных управлений, функцией перехода, которая описывает, как состояние меняется под действием управления, и функцией непосредственного выигрыша или затрат, связанных с данным переходом.
Решение — в контексте динамического программирования это конкретный выбор управления на данном этапе при данном состоянии, который определяет, как система перейдёт в следующее состояние и какой локальный эффект будет получен; однако в более широком смысле решение всей задачи — это не просто отдельные управления, а вся последовательность управлений на всех этапах, которая переводит систему из заданного начального состояния в конечное, причём оптимальное решение среди всех допустимых последовательностей выбирается по критерию минимума или максимума суммарного аддитивного эффекта.
Эффект — это количественная мера последствий принятого решения на данном этапе, которая может выражаться в виде затрат, прибыли, времени, пройденного расстояния, использованного ресурса или любого другого измеримого показателя, причём в задачах динамического программирования этот локальный эффект обычно является аддитивным, то есть общий эффект всей многоэтапной траектории равен сумме локальных эффектов; именно аддитивность позволяет применять принцип оптимальности, поскольку она делает возможным разделение общей цели на независимые части, связанные только через состояния.
- Здесь — метод Р. Беллмана в математическом программировании — оптимальное управление по этапам, уравнение Беллмана.
- В алгоритмах и лаборатории — мемоизация и таблицы для задач вроде рюкзака на одном горизонте. Идея "запомнить подзадачу" родственна, но постановка и термины другие.
Динамическое программирование (ДП) в исследовании операций применяют, когда процесс разбивается на этапы (периоды, шаги, станции), на каждом этапе принимается решение, а эффект накапливается. Вместо перебора всех траекторий используют принцип оптимальности Беллмана — оптимальная стратегия остаётся оптимальной на любом хвосте процесса.
Принцип оптимальности Беллмана — это краеугольный камень динамического программирования, который гласит, что любая часть оптимальной траектории, начинающаяся с любого промежуточного состояния и продолжающаяся до конца процесса, сама является оптимальной для подзадачи, определённой этим состоянием и оставшимся числом этапов; этот принцип позволяет заменять поиск глобально оптимальной полной последовательности решений на рекурсивное построение оптимальных хвостовых политик, что является основой для вывода уравнения Беллмана и делает динамическое программирование столь эффективным для задач с временной или структурной иерархией.
Хвост процесса — это часть многоэтапного процесса, которая начинается с некоторого промежуточного этапа и состояния и продолжается до финального этапа, включая все последующие решения и их эффекты, причём именно хвост процесса является самостоятельной подзадачей, к которой применяется принцип оптимальности; понятие хвоста крайне важно, поскольку оно позволяет записать рекуррентное соотношение, связывающее оптимальную стоимость для текущего состояния с оптимальной стоимостью для следующего состояния, и вся обратная прогонка динамического программирования заключается в последовательном вычислении оптимальных стоимостей для всех возможных хвостов, начиная с финального и двигаясь к начальному.
Идея одной фразой
"Если вы знаете лучший способ пройти от состояния
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 из четырёх этапов
DAG — это аббревиатура для ориентированного ациклического графа, который является естественной структурной моделью для многих задач динамического программирования, поскольку его вершины могут соответствовать состояниям, а дуги — переходам между этапами, причём отсутствие циклов гарантирует конечность процесса и возможность топологической сортировки для однозначного применения рекуррентных соотношений; поиск кратчайшего пути в 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, итоги.