Динамическое программирование в дискретной оптимизации

Принцип оптимальности: разбиваем задачу на подзадачи

Динамическое программирование (ДП) — один из самых элегантных методов дискретной оптимизации. Идея проста и глубока одновременно: оптимальное решение большой задачи строится из оптимальных решений меньших подзадач. Это принцип оптимальности Беллмана. ДП «запоминает» результаты подзадач (memoization), избегая повторных вычислений. Из-за этого ДП работает там, где прямой перебор невозможен.

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

Формулировка: оптимальное решение содержит оптимальные решения всех своих подзадач.

Когда принцип выполнен? Когда подзадачи независимы (решение одной не мешает другой) и структура оптимального решения допускает рекуррентное разложение.

Когда НЕ выполнен? Когда требуется учёт глобальных ограничений (например, задача о комивояжёре — подзадачи связаны между собой через ограничение «посетить каждый город один раз»). Впрочем, и TSP можно решить ДП за O(2ⁿ n²)!

Структура ДП:

Определить состояние (что описывает подзадачу)
Написать рекуррентность (как состояние зависит от меньших состояний)
Определить порядок вычисления (от меньших к большим состояниям)
Восстановить ответ (traceback)

Задача о рюкзаке: классическое ДП

Постановка: n предметов с ценностями cᵢ и весами wᵢ, рюкзак вместимостью W.

Состояние: V[i][w] = максимальная ценность при использовании первых i предметов и вместимости w.

Рекуррентность:

Не берём i-й предмет: V[i][w] = V[i−1][w]
Берём i-й предмет (если w ≥ wᵢ): V[i][w] = V[i−1][w−wᵢ] + cᵢ
V[i][w] = max(V[i−1][w], V[i−1][w−wᵢ] + cᵢ) при w ≥ wᵢ

Начальные условия: V[0][w] = 0 для всех w (нет предметов — нет ценности).

Сложность: O(nW) по времени и памяти — псевдополиномиальная (не полиномиальная, так как W может быть огромным).

Полный разбор (n=3, W=5):

Предметы: (c₁,w₁)=(4,3), (c₂,w₂)=(3,2), (c₃,w₃)=(2,1).

i/w	1	2	3	4	5
0	0	0	0	0	0
1	0	0	4	4	4
2	0	3	4	4	7
3	2	3	5	6	7

V[3][5] = 7. Traceback: V[3][5] = V[2][4]+c₃ (взяли предмет 3, w=1). V[2][4] = V[1][2]+c₂ (взяли предмет 2, w=2). V[1][2] = 0 (предмет 1 весит 3 > 2). Ответ: взяли предметы 2 и 3 (c=5) — нет, пересчитаем.

Traceback: V[3][5]=7: берём предмет 3 (V[2][4]+2=4+2=6? нет) → V[3][5]=V[2][5]=7 (не берём 3). V[2][5]=7: берём предмет 2 (V[1][3]+3=4+3=7). V[1][3]=4: берём предмет 1. Ответ: {1,2}, c=7. ✓

Кратчайшие пути: ДП на графе

Bellman-Ford: d[v] = min_{(u,v)∈E} {d[u] + w(u,v)}.

Состояние: d[k][v] = кратчайший путь от s до v, использующий не более k рёбер.

Рекуррентность: d[k][v] = min{d[k−1][v], min_{(u,v)∈E}(d[k−1][u] + w(u,v))}.

Выполняем n−1 итераций: d[n−1][v] = кратчайший путь.

Обнаружение отрицательного цикла: если d[n][v] < d[n−1][v] для какого-то v — отрицательный цикл!

Floyd-Warshall: все пары кратчайших путей.

Состояние: d[k][i][j] = кратчайший путь от i до j, используя промежуточные вершины из {1,...,k}.

Рекуррентность: d[k][i][j] = min{d[k−1][i][j], d[k−1][i][k] + d[k−1][k][j]}.

Сложность O(V³). Простая реализация в 3 строки кода.

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

Задача: даны строки s₁ и s₂. Найти наибольшую общую подпоследовательность (не обязательно непрерывную).

Состояние: LCS[i][j] = длина НОП строк s₁[1..i] и s₂[1..j].

Рекуррентность:

s₁[i] = s₂[j]: LCS[i][j] = LCS[i−1][j−1] + 1 (берём совпадение)
s₁[i] ≠ s₂[j]: LCS[i][j] = max(LCS[i−1][j], LCS[i][j−1]) (пропускаем один символ)

Применения: биоинформатика — выравнивание последовательностей ДНК (программа BLAST). Системное программирование — алгоритм diff для сравнения файлов в git. Сжатие данных — LZW использует общие подстроки.

TSP через ДП Хелда-Карпа

Состояние: dp[S][v] = длина кратчайшего пути, начинающегося в вершине 1, посещающего все вершины из S ⊆ {2,...,n} ровно по одному разу, и заканчивающегося в v ∈ S.

Рекуррентность: dp[S][v] = min_{u ∈ S{v}} {dp[S{v}][u] + d(u,v)}.

Ответ: min_{v ≠ 1} {dp[{2,...,n}][v] + d(v,1)}.

Сложность: O(2ⁿ · n²) — экспоненциальная, но гораздо лучше O(n!) при переборе. При n=20: 2²⁰ · 400 ≈ 4 · 10⁸ — выполнимо.