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

Динамическое программирование — это метод решения задач путём разбиения их на более простые подзадачи, результат каждой из которых вычисляется однократно и сохраняется для последующего использования. Относится к классу алгоритмов оптимизации, применяется в вычислительной математике, теории управления, экономике и биоинформатике. Ключевая идея метода заключается в том, что оптимальное решение исходной задачи строится из оптимальных решений её подзадач, что позволяет избежать повторных вычислений и значительно сократить временную сложность алгоритма.

История

Основы динамического программирования были заложены американским математиком Ричардом Беллманом в 1950-х годах. Термин «динамическое программирование» впервые появился в его работах 1952 года, а систематическое изложение метода было дано в книге «Динамическое программирование» (1957). Беллман работал в корпорации RAND, где решал задачи оптимизации многошаговых процессов в экономике и военном планировании.

Название «динамическое» было выбрано Беллманом по нескольким причинам: во-первых, оно отражало временной аспект решаемых задач (процессы, развёрнутые во времени); во-вторых, слово «программирование» в то время означало не написание компьютерного кода, а планирование и составление графиков (например, линейное программирование). Беллман также отмечал, что термин был выбран так, чтобы не вызывать негативной реакции у спонсоров — министерства обороны США, которое могло скептически отнестись к «математическим исследованиям».

В 1953 году Беллман сформулировал принцип оптимальности, ставший основой метода: «Оптимальная политика обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную политику относительно состояния, полученного в результате первого решения». Этот принцип лёг в основу уравнения Беллмана — фундаментального соотношения для задач динамического программирования.

В 1950–1960-е годы метод активно развивался: были разработаны алгоритмы для задач управления запасами, распределения ресурсов, сетевого планирования. В 1960-х годах появились работы по применению динамического программирования в теории графов (алгоритм Флойда-Уоршелла для поиска кратчайших путей, 1962) и в задачах распознавания образов. В 1970-е годы метод стал широко использоваться в биоинформатике для выравнивания последовательностей ДНК и белков (алгоритм Нидлмана-Вунша, 1970; алгоритм Смита-Уотермана, 1981).

В СССР и России динамическое программирование развивалось в рамках теории управления и исследования операций. Значительный вклад внесли работы Л. С. Понтрягина (принцип максимума, 1956), В. Г. Болтянского, Р. В. Гамкрелидзе. В 1960–1980-е годы метод применялся для оптимизации производственных процессов, планирования перевозок и управления космическими аппаратами.

Основные понятия и принципы

Принцип оптимальности Беллмана

Принцип оптимальности утверждает, что любое решение, принятое на некотором шаге многошагового процесса, должно быть оптимальным относительно состояния, к которому привело предыдущее решение. Это означает, что оптимальное решение всей задачи может быть построено из оптимальных решений её подзадач.

Рекуррентное соотношение

Центральным элементом динамического программирования является рекуррентное соотношение (уравнение Беллмана), которое связывает оптимальное значение функции для задачи размера \( n \) с оптимальными значениями для задач меньшего размера. Общий вид для дискретных задач:

\[ f(n) = \min_{k} \{ g(k) + f(n-k) \} \]

где \( f(n) \) — оптимальное значение для задачи размера \( n \), \( k \) — возможное решение на данном шаге, \( g(k) \) — стоимость этого решения.

Табуляция и мемоизация

Для реализации динамического программирования используются два подхода:

• Мемоизация (сверху вниз): рекурсивное решение с запоминанием уже вычисленных значений в кэше (обычно в хеш-таблице или массиве).
• Табуляция (снизу вверх): итеративное заполнение таблицы (массива) от меньших подзадач к большим.

Оба подхода эквивалентны по вычислительной сложности, но табуляция часто эффективнее по памяти, так как не требует рекурсивных вызовов.

Условия применимости

Динамическое программирование применимо, если задача обладает двумя свойствами:

1. Оптимальная подструктура: оптимальное решение задачи содержит оптимальные решения подзадач.
2. Перекрывающиеся подзадачи: одни и те же подзадачи решаются многократно в ходе вычислений.

Если подзадачи не перекрываются (каждая решается один раз), задачу проще решить методом «разделяй и властвуй» (например, быстрая сортировка).

Классификация задач

По типу оптимизации

• Задачи на минимум/максимум: поиск кратчайшего пути, минимальной стоимости, максимальной прибыли.
• Задачи на подсчёт количества: число способов достижения цели (например, количество путей в решётке).
• Задачи на проверку существования: возможно ли достичь целевого состояния.

По структуре данных

• Одномерное динамическое программирование: состояние описывается одним параметром (например, длина последовательности). Примеры: числа Фибоначчи, задача о рюкзаке (базовая версия).
• Двумерное динамическое программирование: состояние описывается двумя параметрами. Примеры: задача о рюкзаке с ограничениями, выравнивание последовательностей, поиск наибольшей общей подпоследовательности.
• Многомерное динамическое программирование: три и более параметров состояния. Используется в сложных задачах комбинаторной оптимизации и управления.

По характеру процесса

• Дискретное динамическое программирование: решения принимаются на конечном множестве шагов (например, задача коммивояжёра).
• Непрерывное динамическое программирование: решения принимаются непрерывно во времени (например, задачи оптимального управления).

Алгоритмы и примеры

Классические задачи

Числа Фибоначчи

Простейший пример. \( F(n) = F(n-1) + F(n-2) \), с базой \( F(0)=0, F(1)=1 \). Без динамического программирования рекурсивное решение имеет экспоненциальную сложность \( O(2^n) \), с табуляцией — \( O(n) \).

Задача о рюкзаке (0-1 Knapsack)

Дано \( N \) предметов, каждый с весом \( w_i \) и стоимостью \( v_i \). Необходимо выбрать подмножество предметов так, чтобы суммарный вес не превышал \( W \), а суммарная стоимость была максимальной. Рекуррентное соотношение:

\[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w-w_i] + v_i) \]

где \( dp[i][w] \) — максимальная стоимость для первых \( i \) предметов при весе \( w \). Сложность: \( O(N \cdot W) \).

Наибольшая общая подпоследовательность (LCS)

Даны две строки \( X \) и \( Y \). Найти наибольшую подпоследовательность, общую для обеих строк. Рекуррентное соотношение:

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{если } X[i] = Y[j] \\ \max(dp[i-1][j], dp[i][j-1]), & \text{иначе} \end{cases} \]

Сложность: \( O(m \cdot n) \), где \( m \) и \( n \) — длины строк.

Алгоритм Флойда-Уоршелла

Находит кратчайшие пути между всеми парами вершин во взвешенном графе. Рекуррентное соотношение:

\[ dist[i][j][k] = \min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]) \]

где \( k \) — промежуточная вершина. Сложность: \( O(V^3) \), где \( V \) — число вершин.

Применение в биоинформатике

Динамическое программирование лежит в основе алгоритмов выравнивания последовательностей:

• Алгоритм Нидлмана-Вунша (глобальное выравнивание) — поиск оптимального выравнивания двух последовательностей с учётом штрафов за замены, вставки и делеции.
• Алгоритм Смита-Уотермана (локальное выравнивание) — поиск наиболее похожих участков последовательностей.

Оба алгоритма используют двумерную матрицу и рекуррентные соотношения, аналогичные LCS, но с весами для различных типов мутаций.

Применение

Экономика и управление

• Управление запасами: определение оптимального объёма заказа при случайном спросе.
• Планирование производства: распределение ресурсов между этапами производства для минимизации издержек.
• Инвестиционное планирование: оптимальное распределение капитала между проектами.

Информатика и программирование

• Оптимизация запросов в базах данных: выбор плана выполнения запроса с минимальной стоимостью.
• Обработка естественного языка: алгоритмы Витерби для скрытых марковских моделей (распознавание речи, тегирование частей речи).
• Компьютерное зрение: сегментация изображений, стереозрение (динамическое программирование для поиска соответствий между пикселями).

Теория управления

• Оптимальное управление: расчёт траекторий ракет, космических аппаратов, роботов.
• Адаптивное управление: системы, подстраивающиеся под изменяющиеся условия.

Биоинформатика

• Сравнение геномов: выравнивание последовательностей ДНК и белков.
• Предсказание структуры РНК: поиск вторичной структуры РНК с минимальной свободной энергией.

Ограничения и критика

• Проклятие размерности: при увеличении числа параметров состояния (размерности задачи) объём таблицы растёт экспоненциально. Например, для задачи с 10 параметрами и 10 значениями каждого потребуется \( 10^{10} \) ячеек, что часто превышает доступную память.
• Неприменимость к задачам без оптимальной подструктуры: если оптимальное решение не может быть построено из оптимальных решений подзадач (например, задачи с «памятью» о предыдущих решениях), динамическое программирование не работает.
• Требование дискретности: классическое динамическое программирование требует дискретного представления состояний, что ограничивает его применение в непрерывных задачах без аппроксимации.
• Вычислительная сложность: даже при полиномиальной сложности (например, \( O(N \cdot W) \) для задачи о рюкзаке) при больших значениях параметров (например, \( W = 10^9 \)) алгоритм может быть непрактичен.

Интересные факты

• Ричард Беллман получил премию Тьюринга (1979) в значительной степени за вклад в динамическое программирование.
• Термин «динамическое программирование» изначально не имел отношения к компьютерам — Беллман использовал слово «программирование» в смысле «планирование» (как в «линейном программировании»).
• Алгоритм Витерби (1967), широко используемый в телекоммуникациях и биоинформатике, является частным случаем динамического программирования для скрытых марковских моделей.
• В 2020-е годы динамическое программирование активно применяется в обучении с подкреплением (reinforcement learning), где уравнение Беллмана является основой для алгоритмов Q-обучения и глубоких Q-сетей.

Источники

• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ. 3-е изд. — М.: Вильямс.
• Ахо, А., Хопкрофт, Дж., Ульман, Дж. (2000). Структуры данных и алгоритмы. — М.: Вильямс.
• Нидлман, С., Вунш, К. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443–453.
• Смит, Т., Уотерман, М. (1981). Identification of common molecular subsequences. Journal of Molecular Biology, 147(1), 195–197.
• Флойд, Р. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.