Динамическое программирование: принцип оптимальности Беллмана

Математическим ядром динамического программирования является знаменитый принцип оптимальности Беллмана. Он формулируется следующим образом: каково бы ни было начальное состояние системы и решение, принятое на первом шаге, все последующие решения обязаны составлять оптимальную стратегию поведения относительно того состояния, в котором система оказалась в результате первого шага. Проще говоря, любой фрагмент оптимальной траектории сам по себе должен быть оптимальной траекторией между своими конечными точками. Если бы это было не так, мы могли бы заменить неоптимальный фрагмент на лучший, улучшив тем самым и глобальный результат. Этот кристально ясный логический принцип позволяет строить решение задачи с конца (обратная рекурсия) или с начала (прямая рекурсия), последовательно накапливая оптимальные микро-решения.

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

Классическим примером применения метода является задача о рюкзаке (Knapsack Problem). Имеется набор предметов, каждый из которых обладает определенным весом и ценностью, и рюкзак ограниченной вместимости. Необходимо выбрать такой набор предметов, чтобы максимизировать суммарную ценность, не порвав рюкзак. Если решать эту задачу полным перебором, для n предметов потребуется проверить 2 в степени n комбинаций. Динамическое программирование вводит двумерную матрицу состояний, где строки представляют доступные предметы, а столбцы — текущую вместимость рюкзака от нуля до максимума. Заполняя таблицу шаг за шагом, алгоритм для каждой ячейки выбирает максимум между двумя сценариями: не брать текущий предмет (взять оптимальное решение из предыдущей строки) или взять предмет (добавить его ценность к оптимальному решению для оставшегося места). В результате оптимум находится за время, пропорциональное произведению количества предметов на вместимость рюкзака.

Другой сферой триумфа Беллмана является поиск кратчайших путей на графах (алгоритм Беллмана-Форда). В отличие от алгоритма Дейкстры, подход Беллмана способен корректно обрабатывать графы с ребрами отрицательного веса (что критически важно в финансовых моделях арбитража валют). Алгоритм итеративно ослабляет (релаксирует) оценки расстояний до всех вершин, опираясь на уравнение Беллмана. Однако у этого изящного аппарата есть свой криптонит, который сам Беллман назвал проклятием размерности. Если состояние системы описывается не одним, а несколькими параметрами (многомерный вектор состояния), размер необходимой таблицы мемоизации растет в геометрической прогрессии. Если для управления портфелем из 2 акций требуется таблица 100x100, то для 10 акций потребуется таблица с 10 в 20 степени ячеек, что превышает объем памяти всех компьютеров планеты. Для преодоления этого барьера современные исследователи применяют методы приближенного динамического программирования и обучение с подкреплением (Reinforcement Learning).