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

Поиск кратчайшего пути в ациклическом ориентированном графе

Пусть перед нами стоит задача поиска кратчайших путей от вершины $s$ до всех остальных вершин в ациклическом ориентированном графе. Конечно, можно воспользоваться одним из уже изученных алгоритмов. Есть, однако, и более простое решение с линейным временем работы.

Для любой вершины $v \neq s$ верно следующее равенство:

$$ \operatorname{dist}[v]=\min \left\{d i s t[u]+w_{e}: e=(u, v) \in E\right\} $$

Будем перебирать вершины в порядке топологической сортировки. Тогда все значения dist, встречающиеся в выражении справа, к моменту рассмотрения вершины $v$ уже будут найдены.

1
2
3
4
5
6
7

fill(dist, inf)
dist[s] = 0
for v in topOrder: # рассматриваем вершины в порядке топологической сортировки
    if v == s:
        continue
    for u, w in inEs[v]: # inEs[v] - список входящих в v pëбep
        dist[v] = min(dist[v], dist[u] + w)

Алгоритм рассматривает подзадачи вычисления $\operatorname{dist}[v]$ для конкретной вершины $v$ в порядке увеличения сложности; каждую текущую подзадачу он сводит к нескольким подзадачам попроще, которые уже решены.

Заметим, что ровно таким же способом можно найти и самый длинный путь до каждой вершины; или, например, путь с максимальным произведением длин рёбер.

Метод динамического программирования

Метод динамического программирования так и устроен: задача, которую нужно решить, сводится к подзадачам попроще, те - к подзадачам ещё попроще, и так далее. После этого все подзадачи решаются в правильном порядке. Какой порядок правильный? Построим на подзадачах ориентированный граф: вершины - это подзадачи, а ребро из $a$ в $b$ есть, если для решения подзадачи $b$ требуется сначала решить $a$. Тогда правильный порядок - это топологическая сортировка этого графа (разумеется, в графе на подзадачах не должно быть циклов, иначе никакой порядок не подойдёт, и решить задачу таким методом не удастся). Этот граф, как правило, не строится явно; правильный порядок часто виден сразу и не требует запуска алгоритма топологической сортировки.

Подзадачи мы будем называть состояниями, зависимости между состояниями (рёбра построенного выше графа) - переходами. Начальные состояния - это самые простые подзадачи, решение которых очевидно или известно заранее. В задаче выше начальное состояние $-\operatorname{dist}[s]=0$. Может быть полезно держать в голове аналогию с методом математической индукции: начальное состояние - аналог базы индукции; в методе индукции утверждение для всех остальных состояний доказывается с помощью индукционного перехода, а в методе динамического программирования значения остальных состояний вычисляются с помощью переходов.

На самом деле мы уже встречались с методом динамического программирования: полиномиальный алгоритм вычисления чисел Фибоначчи, алгоритмы Флойда и Форда–Беллмана, решето Эратосфена — все эти алгоритмы можно интерпретировать как динамическое программирование.

Проще всего с числами Фибоначчи: каждое число Фибоначчи соответствует одному состоянию; для того, чтобы узнать значение $n$-го состояния, мы пользуемся значениями $(n-1)$-го и ( $n-2$ )-го.

В алгоритме Флойда состояние - это тройка $(k, i, j): \operatorname{dist}[k, i, j]$ - это длина кратчайшего пути из $i$ в $j$, промежуточные вершины в котором имеют номера меньше $k$. Начальные состояния - тройки с $k=0$, для вычисления $\operatorname{dist}[k+1, i, j]$ нужны $\operatorname{dist}[k, i, j]$, $\operatorname{dist}[k, i, k]$ и $\operatorname{dist}[k, k, j]$.

В алгоритме Форда-Беллмана состояние - это пара $(k, v): \operatorname{dist}[k, v]$ - это длина кратчайшего пути из $s$ в $v$, состоящего из не более чем $k$ рёбер (мы изучали версию алгоритма, соптимизированную по памяти и использующую одномерный массив вместо двумерного).

На задачу определения простых чисел на отрезке $[1, n]$ можно смотреть так: есть переходы из числа во все числа, кратные ему; число простое, если в него нет переходов. Решето Эратосфена рассматривает только переходы из простых чисел в их кратные (потому что этого достаточно); линейная версия решета действует ещё аккуратнее, оставляя лишь по одному переходу в каждое составное число.

Способ вычисления переходов

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

1
2
3
4
5

fill(dist, inf)
dist[s] = 0
for v in topOrder: # рассматриваем вершины в порядке топологической сортировки
    for u, w in es[v]: # es[v] - список исходящих из v рёбер
        dist[u] = min(dist[u], dist[v] + w)

Иногда оказывается, что один из способов оказывается по тем или иным причинам удобнее другого. Рассмотрим для примера такую модельную задачу: пусть $d p[1]=1$, и мы хотим для каждого $x$ от 2 до $n$ вычислить

$$ d p[x]=\sum_{\substack{d < x \\ d \mid x}} d p[d] . $$

Для того, чтобы считать переходы назад, нам придётся найти все делители каждого числа, что требует какой-то дополнительной работы. Считать же переходы вперёд очень просто: для фиксированного $d$ значение $d p[d]$ нужно добавить ко всем значениям состояний, кратных $d$ и не больших $n$. Их легко перебрать простым циклом. При этом суммарное время работы составит

$$ O\left(n+\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n}\right)=O(n \log n) $$

Восстановление ответа

В задаче о кратчайшем пути может требоваться найти не просто длину пути, но и сам путь. Подобное может требоваться и в других задачах: нужно найти не просто число, а какой-то развёрнутый ответ. Как правило, восстановление развёрнутого ответа оказывается эквивалентным восстановлению пути из оптимальных переходов от начального состояния к конечному (мы увидим это на примерах задач). Есть два стандартных способа восстановления ответа. Первым из них мы пользовались в алгоритмах Флойда и ФордаБеллмана: нужно для каждого состояния запомнить, из какого состояния в него был сделан оптимальный переход. Тогда, пользуясь запомненными ссылками, можно откатиться от конечного состояния к начальному и восстановить весь путь.

Второй способ - можно ничего не запоминать, а для того, чтобы найти, откуда был сделан оптимальный переход, просто перебрать все переходы заново (то есть повторить заново всё, что делали при вычислении значения состояния, но запомнить, при рассмотрении какого перехода был найден ответ).

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

fill(dist, -1) # -1 значит, что состояние ещё не рассматривалось
findDist(v):
    if dist[v] != -1:
        return dist[v]
    dist[v] = inf
    for u, w in inEs[v]: # inEs[v] - список входящих в v рёбер
        dist[v] = min(dist[v], findDist(u) + w)
dist[s] = 0
for v = 0..(n - 1): # порядок рассмотрения вершин не важен!
    findDist(v)

Как правило, ленивая версия решения работает медленнее неленивой из-за рекурсивных вызовов. Зато иногда она бывает полезна, когда нужно вычислить значение не всех состояний, а какого-либо одного. Ленивая версия не будет вычислять значения состояний, которые не используются при вычислении требуемого. Если таких состояний много, выигрыш в скорости может быть велик. Модельный пример: значения gcd от всех пар чисел от 0 до $n$ можно вычислить методом динамического программирования, пользуясь соотношением

$$ \operatorname{gcd}(a, b)=\operatorname{gcd}(b, a \bmod b) $$

При этом, как мы знаем, вычисление одного конкретного состояния требует вычисления лишь ещё $O(\log n)$ других состояний. Поэтому если нас интересуют лишь несколько состояний, а не все, намного эффективнее вычислить их лениво.

Задачи

Далее рассмотрим примеры задачи и их решения методом динамического программирования: