Динамическое программирование
- Автор метода
- Richard Bellman
- Год
- 1957
- Тип
- Exact combinatorial optimization via recursive decomposition
- Семейство
- Mathematical programming
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Динамическое программирование (ДП) — это точный метод оптимизации, введенный Ричардом Беллманом в 1957 году для решения многоэтапных задач принятия решений.
Он разлагает сложную задачу на более простые, перекрывающиеся подзадачи, решает каждую подзадачу один раз и сохраняет результаты, чтобы избежать избыточных вычислений. Основанное на Принципе оптимальности, ДП гарантирует глобально оптимальные решения, когда задача обладает перекрывающимися подзадачами и оптимальной подструктурой.
Интуиция метода
Представьте, что вы планируете кратчайший маршрут по городу, сначала находя кратчайшие пути между каждой парой близлежащих перекрестков, а затем объединяя эти небольшие решения вверх. Вместо того чтобы заново исследовать каждый возможный полный маршрут с нуля, вы повторно используете предварительно вычисленные локальные ответы. Динамическое программирование работает так же: оно кэширует решения небольших подзадач, так что построение полного ответа требует только поиска по таблице, а не повторных сложных вычислений.
История
Ричард Беллман ввел термин «динамическое программирование» в 1957 году, работая в корпорации RAND, намеренно выбрав слово «программирование» для обозначения планирования, а не компьютерного кодирования. Сформулированный им Принцип оптимальности стал теоретической основой для теории управления, исследования операций и, позднее, обучения с подкреплением. Классические алгоритмы ДП — алгоритм Дейкстры для поиска кратчайшего пути, алгоритм Витерби и алгоритм Нидлмана-Вунша для выравнивания последовательностей — все они непосредственно вытекают из структуры Беллмана.
Когда применять
Динамическое программирование подходит, когда задача имеет перекрывающиеся подзадачи и оптимальную подструктуру — свойства, общие для последовательного принятия решений, распределения ресурсов, планирования и задач выравнивания строк. Оно требует, чтобы пространство состояний было полностью перечислимым и имело управляемый размер; метод страдает от проклятия размерности, когда переменных состояния много или они непрерывны. Для задач с неразрешимыми пространствами состояний предпочтительны приближенное ДП или обучение с подкреплением.
Ограничения и замечания
- Страдает от проклятия размерности: требования к памяти и времени растут экспоненциально с числом переменных состояния.
- Требует полного предварительного знания структуры переходов и функции вознаграждения; неприменимо к неизвестным средам без аппроксимации.
- Пространство состояний должно быть дискретным или дискретизируемым; непрерывные высокоразмерные задачи требуют аппроксимационных схем, которые жертвуют точностью.
- Формулирование правильного представления состояния и рекуррентного соотношения требует значительного понимания специфики задачи.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Гарантирует точные глобально оптимальные решения для задач, удовлетворяющих Принципу оптимальности.
- Устраняет избыточные вычисления с помощью мемоизации, достигая полиномиального времени от числа состояний.
- Производит явную оптимальную политику, а не просто оптимальную ценность, обеспечивая прямую поддержку принятия решений.
- Широко применимо в различных областях, включая теорию управления, биоинформатику, экономику и исследование операций.
Применение
- Задачи поиска кратчайшего пути и маршрутизации в сетях (варианты алгоритмов Беллмана-Форда, Дейкстры).
- Выравнивание последовательностей в вычислительной биологии (алгоритмы Нидлмана-Вунша, Смита-Ватермана).
- Оптимальное распределение ресурсов и комбинаторные задачи типа задачи о рюкзаке в исследовании операций.
- Распознавание речи и рукописного текста с помощью алгоритма Витерби на скрытых марковских моделях.
- Оптимальное управление и многопериодная оптимизация портфеля в экономике и инженерии.
Как это работает
Как это работает
Общая задача оптимизации выражается в виде рекуррентного соотношения. Для каждого состояния s и этапа принятия решений n, функция ценности V_n(s) равна наилучшему немедленному вознаграждению плюс дисконтированная ценность результирующего следующего состояния. Это уравнение Беллмана формализует Принцип оптимальности: любой подпуть оптимального пути сам по себе должен быть оптимальным.
Формула
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]Рекуррентное соотношение решается итеративно или рекурсивно. При итерации по ценности V^*(s) многократно обновляется для всех состояний до сходимости, используя текущую оценку значений соседних состояний. Каждое обновление заменяет старое значение наилучшим достижимым вознаграждением плюс будущей ценностью, распространяя информацию об оптимальности по пространству состояний.
Формула
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)Вычисленные значения хранятся в таблице, индексированной по состоянию. Терминальные состояния получают базовое значение ноль (или известное вознаграждение), а все остальные записи заполняются по мере решения подзадач. Мемоизация гарантирует, что каждое состояние оценивается не более одного раза, сокращая экспоненциальный рекурсивный поиск до полиномиального времени от числа состояний и этапов.
Формула
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}После завершения таблицы ценностей оптимальная политика pi^*(s) восстанавливается простым жадным проходом: для каждого состояния выбирается действие, которое максимизирует немедленное вознаграждение плюс сохраненную ценность следующего состояния. Это однопроходное извлечение вычислительно дешево и дает детерминированное, глобально оптимальное правило принятия решений.
Формула
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]Частые ошибки
- Определение недостаточно выразительного представления состояния приводит к некорректным рекуррентным соотношениям и субоптимальным решениям.
- Путаница между нисходящей мемоизацией и восходящей табуляцией может привести к ошибкам переполнения стека или неправильному порядку оценки подзадач.
- Применение ДП к задачам, не обладающим оптимальной подструктурой (например, самый длинный путь в общем графе), приводит к некорректным результатам без предупреждения.
- Игнорирование численной точности в вычислениях кумулятивного вознаграждения может вызвать тонкие ошибки оптимальности в реализациях с плавающей запятой.
Часто задаваемые вопросы
В чем разница между динамическим программированием и методом разделяй и властвуй?
Оба метода разлагают задачи на подзадачи, но метод разделяй и властвуй предполагает независимые подзадачи, решаемые естественно только один раз. Динамическое программирование нацелено на перекрывающиеся подзадачи — одна и та же подзадача появляется в нескольких ветвях — и мемоизирует результаты, чтобы избежать избыточной работы. Без перекрывающихся подзадач ДП не дает вычислительного преимущества перед прямым рекурсивным подходом.
Когда следует использовать нисходящую мемоизацию вместо восходящей табуляции?
Нисходящая мемоизация проще в реализации непосредственно из рекуррентного соотношения и вычисляет только необходимые подзадачи, что выгодно для разреженных пространств состояний. Восходящая табуляция избегает накладных расходов на рекурсию и ограничений стека, подходит для плотных пространств состояний и часто оказывается быстрее на практике. Выбирайте нисходящий подход, когда трудно предсказать набор необходимых подзадач, восходящий — когда все подзадачи будут необходимы.
Как динамическое программирование связано с обучением с подкреплением?
Классическое ДП требует полностью известной модели марковского процесса принятия решений (вероятности переходов и вознаграждения). Обучение с подкреплением расширяет идеи ДП на ситуации, где модель неизвестна, вместо этого используя выборку опыта. Алгоритмы, такие как Q-обучение и методы градиента политики, являются приближенными процедурами ДП, которые изучают функции ценности из взаимодействия, а не из явной модели.
Похожие методы
Источники
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN: 978-0-691-07951-6Скопировано.